Implementacja SHA-1: niespodziewane zakończenie programu (SIGABRT) po poprawnym obliczeniu hashu

Question

Witam,

Próbuję zaimplementować algorytm SHA-1 w języku C++, docelowo z zamiarem przeniesienia na mikrokontroler AVR jako część "sprzętowego Google Authenticatora". Na razie testuję go jednak na komputerze i natrafiłem na problem, którego przyczyny nie mogę zlokalizować. Otóż tworzę obiekt klasy Sha, wysyłam testowe wejście w postaci tablicy 32-bitowych nieujemnych liczb całkowitych i jej długości do publicznej funkcji calculate_hash(), która zwraca wskaźnik na analogiczną tablicę 5-elementową - 160-bitowy hash. Wynik operacji wyświetlam na standardowym wyjściu korzystając ze strumienia std::cout. Do tego momentu wszystko zdaje się działać - na podstawie kilku losowych testów wyniki są prawidłowe. Jednak potem, zamiast normalnie zakończyć program z kodem 0, niespodziewanie kończy on wykonywanie z innym kodem. Podejrzewam, że problem może być związany z niepoprawnym korzystaniem przeze mnie z dynamicznej alokacji pamięci. Poniżej wyjście w konsoli po normalnym uruchomieniu.

*** Error in `./Sha_rev3': double free or corruption (fasttop): 0x0000000001caac40 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7fcf6af367e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7fcf6af3f37a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7fcf6af4353c]
./Sha_rev3[0x400d8d]
./Sha_rev3[0x400b4b]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7fcf6aedf830]
./Sha_rev3[0x400949]
======= Memory map: ========
00400000-00402000 r-xp 00000000 00:30 135319                             /home/mduchalski/Dokumenty/Cpp/Sha_rev3/bin/Debug/Sha_rev3
00601000-00602000 r--p 00001000 00:30 135319                             /home/mduchalski/Dokumenty/Cpp/Sha_rev3/bin/Debug/Sha_rev3
00602000-00603000 rw-p 00002000 00:30 135319                             /home/mduchalski/Dokumenty/Cpp/Sha_rev3/bin/Debug/Sha_rev3
01c99000-01ccb000 rw-p 00000000 00:00 0                                  [heap]
7fcf64000000-7fcf64021000 rw-p 00000000 00:00 0 
7fcf64021000-7fcf68000000 ---p 00000000 00:00 0 
7fcf6abb6000-7fcf6acbe000 r-xp 00000000 08:03 6034310                    /lib/x86_64-linux-gnu/libm-2.23.so
7fcf6acbe000-7fcf6aebd000 ---p 00108000 08:03 6034310                    /lib/x86_64-linux-gnu/libm-2.23.so
7fcf6aebd000-7fcf6aebe000 r--p 00107000 08:03 6034310                    /lib/x86_64-linux-gnu/libm-2.23.so
7fcf6aebe000-7fcf6aebf000 rw-p 00108000 08:03 6034310                    /lib/x86_64-linux-gnu/libm-2.23.so
7fcf6aebf000-7fcf6b07f000 r-xp 00000000 08:03 6034315                    /lib/x86_64-linux-gnu/libc-2.23.so
7fcf6b07f000-7fcf6b27f000 ---p 001c0000 08:03 6034315                    /lib/x86_64-linux-gnu/libc-2.23.so
7fcf6b27f000-7fcf6b283000 r--p 001c0000 08:03 6034315                    /lib/x86_64-linux-gnu/libc-2.23.so
7fcf6b283000-7fcf6b285000 rw-p 001c4000 08:03 6034315                    /lib/x86_64-linux-gnu/libc-2.23.so
7fcf6b285000-7fcf6b289000 rw-p 00000000 00:00 0 
7fcf6b289000-7fcf6b29f000 r-xp 00000000 08:03 6033977                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fcf6b29f000-7fcf6b49e000 ---p 00016000 08:03 6033977                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fcf6b49e000-7fcf6b49f000 rw-p 00015000 08:03 6033977                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fcf6b49f000-7fcf6b611000 r-xp 00000000 08:03 535345                     /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7fcf6b611000-7fcf6b811000 ---p 00172000 08:03 535345                     /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7fcf6b811000-7fcf6b81b000 r--p 00172000 08:03 535345                     /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7fcf6b81b000-7fcf6b81d000 rw-p 0017c000 08:03 535345                     /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7fcf6b81d000-7fcf6b821000 rw-p 00000000 00:00 0 
7fcf6b821000-7fcf6b847000 r-xp 00000000 08:03 6034293                    /lib/x86_64-linux-gnu/ld-2.23.so
7fcf6ba27000-7fcf6ba2c000 rw-p 00000000 00:00 0 
7fcf6ba43000-7fcf6ba46000 rw-p 00000000 00:00 0 
7fcf6ba46000-7fcf6ba47000 r--p 00025000 08:03 6034293                    /lib/x86_64-linux-gnu/ld-2.23.so
7fcf6ba47000-7fcf6ba48000 rw-p 00026000 08:03 6034293                    /lib/x86_64-linux-gnu/ld-2.23.so
7fcf6ba48000-7fcf6ba49000 rw-p 00000000 00:00 0 
7ffe7cdac000-7ffe7cdcd000 rw-p 00000000 00:00 0                          [stack]
7ffe7cdee000-7ffe7cdf0000 r--p 00000000 00:00 0                          [vvar]
7ffe7cdf0000-7ffe7cdf2000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
e2512172abf8cc9f67fdd49eb6cacf2df71bbad3Przerwane

Próbowałem zlokalizować go korzystając z debuggera, ale nie wskazuje on na żadną konkretną linię, a jedynie wyświetla takie okno "Call stack" z takim tekstem:

#0 0x7ffff74aa428	__GI_raise(sig=sig@entry=6) (../sysdeps/unix/sysv/linux/raise.c:54)
#1 0x7ffff74ac02a	__GI_abort() (abort.c:89)
#2 0x7ffff74ec7ea	__libc_message(do_abort=do_abort@entry=2, fmt=fmt@entry=0x7ffff7605e98 "*** Error in `%s': %s: 0x%s ***\n") (../sysdeps/posix/libc_fatal.c:175)
#3 ??	0x00007ffff74f537a in malloc_printerr (ar_ptr=<optimized out>, ptr=<optimized out>, str=0x7ffff7605f60 "double free or corruption (fasttop)", action=3) (malloc.c:5006)
#4 ??	_int_free (av=<optimized out>, p=<optimized out>, have_lock=0) (malloc.c:3867)
#5 0x7ffff74f953c	__GI___libc_free(mem=<optimized out>) (malloc.c:2968)
#6 0x400d8d	Sha::~Sha(this=0x7fffffffe4f0, __in_chrg=<optimized out>) (/home/mduchalski/Dokumenty/Cpp/Sha_rev3/main.cpp:27)
#7 0x400b4b	main() (/home/mduchalski/Dokumenty/Cpp/Sha_rev3/main.cpp:132)

Byłbym niezmiernie wdzięczny za wszelką pomoc w zlokalizowaniu problemu. Korzystam z: G++ w wersji 5.4.0 (-std=c++11), GDB 7.11.1, Code::Blocks 16.01, wszystko na Linux Mint 18.2 na platformie x86_64. Poniżej mój pełny kod:

#include <iostream>
#include <cstdint>

using namespace std;

uint32_t leftrotate(uint32_t n, uint8_t shift)
{
    return (n << shift) | (n >> (32 - shift));
}

class Sha
{
public:
    Sha()
    {
        // set initial values
        h = new uint32_t [5];

        h[0] = 0x67452301;
        h[1] = 0xEFCDAB89;
        h[2] = 0x98BADCFE;
        h[3] = 0x10325476;
        h[4] = 0xC3D2E1F0;
    }
    ~Sha()
    {
        delete [] h;
    }

    uint32_t * calculate_hash(uint32_t * msg, uint8_t len) // to-do: make a friend function
    {
        prepare(msg, len);

        loop(msg, len);

        delete [] msg;

        return h;
    }
private:
    uint32_t * h;

    void prepare(uint32_t * &msg, uint8_t &len)
    {
        // declaring some variables
        uint8_t    i;
        uint32_t   old_len = len;
        uint32_t * temp;

        // determining new length
        len  = old_len + 16 - (old_len % 16);
        temp = new uint32_t [len];

        // copying over original message
        for (i = 0; i < old_len; i++)
            temp[i] = msg[i];

        // appending '1'
        temp[old_len] = 0x80000000;

        // zero-padding until 512-bits
        for (i = old_len + 1; i < len; i++)
            temp[i] = 0x00000000;

        // appending old_len at the end
        temp[len - 1] = 32 * old_len;

        // cleanup and final processing
        msg = temp;
    }
    void loop(uint32_t * &msg, uint8_t &len)
    {
        // declaring some variables
        uint32_t * state = new uint32_t [80];
        uint32_t   a, b, c, d, e, f, k, temp;
        uint8_t    i, j;

        for (i = 0; i < len; i += 16)
        {
            // copying current block to state
            for (j = i; j < i + 16; j++)
                state[j - 16 * i] = msg[j];

            // padding the rest of state as per specification
            for (j = 16; j < 80; j++)
                state[j] = leftrotate(state[j-3] ^ state[j-8] ^ state[j-14] ^ state[j-16], 1);

            // initialize values for the current block
            a = h[0], b = h[1], c = h[2], d = h[3], e = h[4];

            // main loop
            for (j = 0; j < 80; j++)
            {
                if (j < 20) {
                    f = (b & c) | ( (~b) & d );
                    k = 0x5A827999;
                } else if (j < 40) {
                    f = b ^ c ^ d;
                    k = 0x6ED9EBA1;
                } else if (j < 60) {
                    f = (b & c) | (b & d) | (c & d);
                    k = 0x8F1BBCDC;
                } else {
                    f = b ^ c ^ d;
                    k = 0xCA62C1D6;
                }

                temp = leftrotate(a, 5) + f + e + k + state[j];
                e = d;
                d = c;
                c = leftrotate(b, 30);
                b = a;
                a = temp;
            }

            // add up results
            h[0] += a, h[1] += b, h[2] += c, h[3] += d, h[4] += e;
        }
    }
};

int main()
{
    uint32_t* test;
    uint32_t* rtest;
    uint8_t  len = 1;

    test = new uint32_t [len];
    for (uint8_t i = 0; i < len; i++)
        test[i] = 0x41414141;

    Sha tescik;
    rtest = tescik.calculate_hash(test, len);

    for (uint8_t j = 0; j < 5; j++)
        cout << hex << rtest[j];

    delete [] test;
    delete [] rtest;

    return 0;
}

EDIT - W pełni działający kod po kilku poprawkach, w razie gdyby ktoś przeglądał to pytanie w przyszłości:

#include <iostream>
#include <cstdint>

using namespace std;

uint32_t leftrotate(uint32_t n, uint8_t shift)
{
    return (n << shift) | (n >> (32 - shift));
}

class Sha
{
public:
    Sha()
    {
        // set initial values
        h = new uint32_t [5];

        h[0] = 0x67452301;
        h[1] = 0xEFCDAB89;
        h[2] = 0x98BADCFE;
        h[3] = 0x10325476;
        h[4] = 0xC3D2E1F0;
    }
    ~Sha()
    {
        delete [] h;
        h = nullptr;
    }

    uint32_t * calculate_hash(uint32_t * msg, uint8_t len) // to-do: make a friend function
    {
        prepare(msg, len);

        loop(msg, len);

        delete [] msg;
        msg = nullptr;

        return h;
    }
private:
    uint32_t * h;

    void prepare(uint32_t * &msg, uint8_t &len)
    {
        // declaring some variables
        uint8_t    i;
        uint32_t   old_len = len;
        uint32_t * temp;

        // determining new length
        len  = old_len + 16 - (old_len % 16);
        temp = new uint32_t [len];

        // copying over original message
        for (i = 0; i < old_len; i++)
            temp[i] = msg[i];

        // appending '1'
        temp[old_len] = 0x80000000;

        // zero-padding until 512-bits
        for (i = old_len + 1; i < len; i++)
            temp[i] = 0x00000000;

        // appending old_len at the end
        temp[len - 1] = 32 * old_len;

        // cleanup and final processing
        msg = temp;
    }
    void loop(uint32_t * &msg, uint8_t &len)
    {
        // declaring some variables
        uint32_t * state = new uint32_t [80];
        uint32_t   a, b, c, d, e, f, k, temp;
        uint8_t    i, j;

        for (i = 0; i < len; i += 16)
        {
            // copying current block to state
            for (j = i; j < i + 16; j++)
                state[j - i] = msg[j];

            // padding the rest of state as per specification
            for (j = 16; j < 80; j++)
                state[j] = leftrotate(state[j-3] ^ state[j-8] ^ state[j-14] ^ state[j-16], 1);

            // initialize values for the current block
            a = h[0], b = h[1], c = h[2], d = h[3], e = h[4];

            // main loop
            for (j = 0; j < 80; j++)
            {
                if (j < 20) {
                    f = (b & c) | ( (~b) & d );
                    k = 0x5A827999;
                } else if (j < 40) {
                    f = b ^ c ^ d;
                    k = 0x6ED9EBA1;
                } else if (j < 60) {
                    f = (b & c) | (b & d) | (c & d);
                    k = 0x8F1BBCDC;
                } else {
                    f = b ^ c ^ d;
                    k = 0xCA62C1D6;
                }

                temp = leftrotate(a, 5) + f + e + k + state[j];
                e = d;
                d = c;
                c = leftrotate(b, 30);
                b = a;
                a = temp;

            }
            // add up results
            h[0] += a, h[1] += b, h[2] += c, h[3] += d, h[4] += e;
        }
        delete [] state;
        state = nullptr;
    }
};

int main()
{
    uint32_t* test;
    uint32_t* rtest;
    uint8_t  len = 100;

    test = new uint32_t [len];
    for (uint8_t i = 0; i < len; i++)
        test[i] = 0x41414141;

    Sha tescik;

    rtest = tescik.calculate_hash(test, len);

    for (uint8_t j = 0; j < 5; j++)
        cout << hex << rtest[j];

    delete [] test;
    test = nullptr;

    return 0;
}

 

Answer 1

Funkcja calculate_hash zwraca pointer h, który jest przypisywany do pointera rtest, na którym pod koniec maina jest wywoływane delete. Następnie w destruktorze Sha jest wywoływane delete na tym samy adresie. double free. Usuń: 

delete [] rtest;

 

Answer 2

Hmm.. a jesteś pewien że na AVR chcesz obsłużyć dynamiczną alokację? Na tym MCU należy samodzielnie napisać new i delete (jeśli nie mówimy o Arduino) i zgodnie z tym co widzę chcesz na nim użyć C++.

Nie lepiej zrobić statyczne pole w tej klasie? Chyba że masz mieć kilka instancji...

Comments

Dzięki za odpowiedź i sugestie. Szczerze mówiąc stawiam dopiero pierwsze kroki w programowaniu jako takim i w AVRach konkretnie, dlatego planowałem użyć IDE i bootloadera Arduino.