Minneproblemer / heap corruption

[etse]

Hei.

 

Jeg holder på med å sette opp et script som skal kryptere tekst-strenger med en ganske sterk-RSA kryptering, altså en nøkkel på cirka 1024 bits. For å få til dette har jeg begynt med å lage en klasse som skal tilsvare nøkkelen (altså begge private-keysene og public-keyen). JEg har og generert funksjoner i denne klassen som skal generere en tilfeldig RSA-nøkkel - og dette blir gjort med å velge 2 tilfeldige 512-bits tall, og så sjekke om "Største felles divisor" mellom tallene er 1. Siden jeg gjør alt på binær-form bruker jeg til dette steins algoritme, som man finner på wikipedia.

 

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

 

Main-fila:

#include <iostream>
#include "rsa.h"

int main()
{
RSAkey key;
key.create_random();

return 1;
}

 

rsa.h:

// This is the header file.
// It holds the classes needed for RSA-encryption

#ifndef RSA_H
#define RSA_H

// Keys terminated with -1 - Least significant bit first (100 = 1, and 001 = 4)
class RSAkey
{
public:
int set_key(int *private1, int *private2); // Sets a new key
int create_random(); // Creates a random key
int *n, *p, *q; // n=private1, p=private2, q=public
int bit;

protected:
int calculate_public(); // Calculates public-key
int check_prime(); // Checks if GCD is 1
int bin_shift(int *num); // A binary shift
int *diff(int *num1, int *num2); // return num2-num1
int min(int *u, int *v); // Returns 1 if u is min, 0 if v
int is_zero(int *num); // checks if num is zero
};
#endif

 

RSA.cpp:

http://pastebin.com/VZERZywH

la den på pastebin siden den var såpass stor

 

-----------

Calculate_public regner ut public-keyen ved å ganke sammen n og p (som er private-keys) på binær form. Gjort en del unit-testing på den og den ser ut til å fungere helt fint.

 

bin_shift tar å flytter alle binære tallene et hakk. Altså å dele på 2 i binær-form

 

diff - binær-subtraksjon. Returnerer et array med differansen

 

min - sjekker hvilket tall av u og v som er størst, på binær

 

is_zore - returnerer 1 hvis tallet gitt som input er null (tenk binær-array)

 

check_prime - sjekker om 2 tall er parvis-prime ved bruk av binær-GCD algoritme (som er basert på den euklidske algoritmen). Det er her jeg har problemer. Den gir meg heap-corruption når jeg prøve å frigi noe midlertidige minne som jeg ikke lenger trenger.

 

 

Noen som klarer å se hvorfor den gir feilmelding der?

[Dinosauromann]

Vet ikke om bare det er det som er feilen, men i check_prime allokerer du et array med "new" og sletter det med "free()", ting som allokeres med new bør slettes med delete og motsatt. http://www.parashift.com/c++-faq-lite/freestore-mgmt.html#faq-16.3

Endret 3. september 2010 av egebokk

[etse]

har fikset det nå, og endret til å frigi-minne med bruk av delete, men det gjorde i praksis ingen forskjell. Får samme feil på samme plass - altså linje 86.

 

ny kode: http://pastebin.com/Uh9nF5Qy

 

84. tmp = v;

85. v = diff(u,v);

86. delete tmp;

[zotbar1234]

har fikset det nå, og endret til å frigi-minne med bruk av delete, men det gjorde i praksis ingen forskjell. Får samme feil på samme plass - altså linje 86.

 

int RSAkey::check_prime()
{
       int *tmp, *u, *v;
       u = new int[(bit/2)+1];
       v = new int[(bit/2)+1];
       // ... 

       while(is_zero(v)!=1)
       {
               while(v[(bit/2)-1]==1)
                       bin_shift(v);
               if(min(u,v)==1)
               {
                       tmp = v;
                       v = diff(u,v);
                       delete tmp;

 

Kan det være fordi du frigjør minne med delete, enda blokken var allokert med new[] ?

[etse]

har fikset det nå, og endret til å frigi-minne med bruk av delete, men det gjorde i praksis ingen forskjell. Får samme feil på samme plass - altså linje 86.

 

int RSAkey::check_prime()
{
       int *tmp, *u, *v;
       u = new int[(bit/2)+1];
       v = new int[(bit/2)+1];
       // ... 

       while(is_zero(v)!=1)
       {
               while(v[(bit/2)-1]==1)
                       bin_shift(v);
               if(min(u,v)==1)
               {
                       tmp = v;
                       v = diff(u,v);
                       delete tmp;

 

Kan det være fordi du frigjør minne med delete, enda blokken var allokert med new[] ?

og hva er alternativet? =/ bruke free? men han som postet i stad viser til ne kilde som sier man ikke skal bruke free, men delete.

[worseisworser]

har fikset det nå, og endret til å frigi-minne med bruk av delete, men det gjorde i praksis ingen forskjell. Får samme feil på samme plass - altså linje 86.

 

int RSAkey::check_prime()
{
       int *tmp, *u, *v;
       u = new int[(bit/2)+1];
       v = new int[(bit/2)+1];
       // ... 

       while(is_zero(v)!=1)
       {
               while(v[(bit/2)-1]==1)
                       bin_shift(v);
               if(min(u,v)==1)
               {
                       tmp = v;
                       v = diff(u,v);
                       delete tmp;

 

Kan det være fordi du frigjør minne med delete, enda blokken var allokert med new[] ?

og hva er alternativet? =/ bruke free? men han som postet i stad viser til ne kilde som sier man ikke skal bruke free, men delete.

 

 

malloc -> free

new -> delete

new[] -> delete[]

[etse]

takker for at dere prøver å hjelpe

 

Feilmeldingen jeg får er spesifikt:

HEAP[rsa.exe]: Heap block at 00514758 modified at 00514F88 past requested size of 828

Windows has triggered a breakpoint in rsa.exe.

 

This may be due to a corruption of the heap, which indicates a bug in rsa.exe or any of the DLLs it has loaded.

 

This may also be due to the user pressing F12 while rsa.exe has focus.

 

The output window may have more diagnostic information.

 

Den peker så på linja: delete[(bit/2)+1] tmp;

 

Har prøvd å erstatte den med følgende:

delete tmp;

delete[] tmp;

delete[513] tmp; - men alle gjør det samme.

 

Noen som har tips til hvordan jeg kan fortsette debuggingen for å finne feilen? =/ jeg er helt blank her

Endret 3. september 2010 av etse

[zotbar1234]

ble dobbelpost.

Endret 4. september 2010 av zotbar1234

[zotbar1234]

Den peker så på linja: delete[(bit/2)+1] tmp;

 

Har prøvd å erstatte den med følgende:

delete tmp;

delete[] tmp;

delete[513] tmp; - men alle gjør det samme.

 

Nei, de gjør ikke det samme (spørsmål -- hvordan er de forskjellige?). Nei, du har ikke prøvd den siste varianten (fordi at da ville du ha observert at kompilatoren ville ha klaget).

 

For det første, gå gjennom *alle* allokeringer du gjør, og sjekk at new[] blir faktisk parret med delete[]. Du har riktignok fikset *ett* sted, men det er, nokså opplagt, ikke alt.

 

For det andre, kan det være en ide å faktisk sjekke at du aldri indekserer deg forbi arrayens grenser? I diff, gjør du bl.a. dette:

 

   newnum[i]=0;
   int j=1;
   while(num2[i+j]==0)
       j++;
   num2[i+j]=0;

 

Jeg vil anbefale å sjekke at i+j er faktisk innen det objektet som num2 peker på, fordi at valgrind rapporterer nemlig dette:

 

==4766== 44343 errors in context 10 of 11:
==4766== Invalid read of size 4
==4766==    at 0x400EE2: RSAkey::diff(int*, int*) (rsa.cpp:153)
==4766==    by 0x400BDD: RSAkey::check_prime() (rsa.cpp:88)
==4766==    by 0x4009A1: RSAkey::create_random() (rsa.cpp:37)
==4766==    by 0x40126F: main (main.cpp:7)

 

Mao. 44'343 leseaksesser til minne som du ikke har tilgang til. Hva tror du _det_ kommer av?

 

For det tredje, valgrind gir veldig gode råd. Bl.a. om feil bruk av delete[]. Og spesielt bør du legge merke til hva du gjør i diff(), mtp hvor mange advarsler valgrind kommer om ang minneaksesser (read og write) i akkurat den funksjonen.

 

For det fjerde, jeg fatter ikke hvorfor du bruker -1 som markør, all den tid du *vet* eksakt hvor store arrayene dine er. Ej heller forstår jeg hvorfor du bruker new[]/delete[]. Man har std::vector til sånt. Da ville du nemlig ha sluppet problematikken med new/delete.

[etse]

Takker for veldig god hjelp Jeg fikk vekk alle heap og minne-problemer nå ved å konsekvent alltid dobbeltsjekke at jeg aldri leste utover minne.

 

Du spør hvorfor jeg slutter arrayet med -1, så er dette fordi jeg geentlig begynte med strenger osv, men som du sier er det helt bortkastet når jeg vet lengden på arrayene, så dette fjernet jeg.

 

Vektorer har jeg desverre ikke sett på, og det er forklaringen på at jeg ikke bruker det. Holderp å ålesem eg opp på C++, etter egentlig kun å ha brukt Ansi-C og Python frem til nå, derfor henger mye fra C igjen, som jeg må klare å venne meg av med.

 

Men ja, nå sitterj eg kun igjen med noen problemer med evighetslooper, men har funnet noen problemer med algoritmen som er litt feil - og er sikkert flere. Så dette skal jeg klare å finne ut av

 

Takker for kjempe god hjelp.

[zotbar1234]

Du spør hvorfor jeg slutter arrayet med -1, så er dette fordi jeg geentlig begynte med strenger osv,

 

Det er jo ikke nødvendig med -1 som markør for std::string heller?

 

Vektorer har jeg desverre ikke sett på, og det er forklaringen på at jeg ikke bruker det.

 

Her har du en ypperlig mulighet (bruker fill_n men ikke vector? Hmmm... ) F.eks denne tråden, om enn gammel, inneholder en rekke nyttige tips. Men muligens ikke hvordan du sporer opp dine SIGSEGVs (som, etter å ha sett litt på koden, kan potensielt skyldes at du overskriver tilfeldige steder i nærheten av arrayene du allokerer med 0 da du går utenfor arrayenes grenser).

 

valgrind er selvsagt ikke en panasé, men kan ofte være en bra indikasjon på hvilke minneproblemer du sliter med.

[etse]

Jeg har fått den til å fungere nå, evighetsloopen viste deg å være en liten bagatell hvor en for-loop på slutten av check_prime startet på 0 i stede for 1 (jeg skulle egentlig sjekke om tallet var 1, men jeg sjekket om tallet var 0 - og største felles divisor blir aldri 0)

 

fill_n bruker jeg fordi jeg tilfeldigvis fant dne på google når jeg lette etter en måte å fylle opp et array på enkelt i c++, selv når jeg ikke visste størrelsen på arrayet.

 

i strenger terminerer man ikke med -1, det er sant. men man terminerer de vel med

'\n' slik som man char-arrays? Det hele begynte med at jeg ikke var sikker på hvor store områder jeg måtte allokere til nøklene, og det vet jeg egentlig ikke 100% sikkert nå heller. Jeg har unngått det problemet ved å lagre hvor store de er i en variabel i klassen slik at alle metodene kan sjekke dette. I begynnelsen ønsket jeg at funksjonene skulle være universale og jeg ønsket ikke å bruke denne variabelen - men da skapte mer problemer enn det gjorde nytte for seg så jeg gikk bor i fra det - men sluttet ikke med å "terminere" arrayene.

 

Problemet er at jeg enda ikke har fått lest meg opp på standatrdbiblioteket, så vektorer o.s.v. er det neste som kommer Kanskje jeg endrer fra å bruke arrays tilvektorer da, om det har noen stor nytte (og om jeg føler for å ta meg tid til det).

[zotbar1234]

i strenger terminerer man ikke med -1, det er sant. men man terminerer de vel med

'\n' slik som man char-arrays?

 

Jeg tror du mener '\0'. Men nei, det foreligger intet slik krav for std::string (selv om en implementasjon kan tenkes å gjøre det, om ikke annet så for å støtte std::string.c_str() "lett").

[etse]

i strenger terminerer man ikke med -1, det er sant. men man terminerer de vel med

'\n' slik som man char-arrays?

 

Jeg tror du mener '\0'. Men nei, det foreligger intet slik krav for std::string (selv om en implementasjon kan tenkes å gjøre det, om ikke annet så for å støtte std::string.c_str() "lett").

Ja, det su sier stemmer, jeg mente nok '\0', tenkte på samme terminering på "strings (char'arrays) i C. Men merker at det største problemet med C++ er at det er for likt C, så jeg tenker alt for mye C og for lite c++ når jeg holder på med det =/

[Dead_Rabbit]

Btw, jeg har ikke sett noe særlig på koden din, men generelt i forbindelse med implementering av kryptografiske algoritmer: bruk allerede-eksisterende kryptobiblioteker fremfor å implementer det selv. Det er _veldig_ lett å gjøre feil som er vanskelige å oppdage, og som knekker krypteringa. Hvis det er for gøy/læring, blir det jo selvfølgelig noe annet.

[etse]

Som du sier på slutten, så er hele poenget å lære. Jeg har egentlig ingenting jeg skal bruke dette til, utenom å kanskje implementere det i en form for benchmark.