Pytanie Zalecany sposób na wyśledzenie macierzy poza związanym dostępem / zapis w programie C


Rozważ napisanie implementacji dla jakiegoś mało oczywistego algorytmu w C. Na przykład, niech to będzie rekurencyjny quicksort, który znalazłem w książce K. N. Kinga "C Programming: A Modern Approach, 2nd Edition", że jest ona dostępna w tutaj. Najciekawsza część składa się z dwóch następujących definicji:

void quicksort(int a[], int low, int high)
{
    int middle;

    if (low >= high)
        return;

    middle = split(a, low, high);
    quicksort(a, low, middle - 1);
    quicksort(a, middle + 1, high);
}

int split(int a[], int low, int high)
{
    int part_element = a[low];

    for (;;) {
       while (low < high && part_element <= a[high])
           high--;
       if (low >= high)
           break;
       a[low++] = a[high];

       while (low < high && a[low] <= part_element)
           low++;
       if (low >= high)
           break;
       a[high--] = a[low];
    }

    a[high] = part_element;
    return high;
}

Obie while pętle można zoptymalizować poprzez usunięcie low < high testy:

for (;;) {
    while (part_element < a[high])
        high--;
    if (low >= high)
        break;
    a[low++] = a[high];
    a[high] = part_element;

    while (a[low] <= part_element)
        low++;
    if (low >= high)
        break;
    a[high--] = a[low];
    a[low] = part_element;
}

Jaki jest zalecany sposób, aby upewnić się, że każdy dostęp lub zapis do tablicy (przydzielone na stos) jest rzeczywiście poprawny (tj. nie powodujący nieokreślonego zachowania)? Próbowałem już:

  • ręcznie debuguj przy pomocy gdb na niektórych rzeczywistych danych
  • przekazać kod źródłowy do narzędzi do analizy statycznej, takich jak split lub cppcheck
  • valgrind z --tool=exp-sgcheck przełącznik

Na przykład mając pięć tablic elementów {8, 1, 2, 3, 4}:

#define N 5

int main(void)
{
    int a[N] = {8, 1, 2, 3, 4}, i;

    quicksort(a, 0, N - 1);

    printf("After sort:");
    for (i = 0; i < N; i++)
        printf(" %d", a[i]);
    putchar('\n');

    return 0;
}

Wynik jest (z całą pewnością zależny od implementacji):

After sort: 1 1 2 4 8

1. GDB

(gdb) p low
$1 = 3
(gdb) p high
$2 = 4
(gdb) p a[low]
$3 = 1
(gdb) p part_element
$4 = 8
(gdb) s
47              low++;
(gdb) s
46          while (a[low] <= part_element)
(gdb) s
47              low++;
(gdb) s
46          while (a[low] <= part_element)
(gdb) p low
$5 = 5
(gdb) p high
$6 = 4
(gdb) bt full
#0  split (a=0x7fffffffe140, low=5, high=4) at qsort.c:46
        part_element = 8
#1  0x00000000004005df in quicksort (a=0x7fffffffe140, low=0, high=4) at qsort.c:30
        middle = <value optimized out>
#2  0x0000000000400656 in main () at qsort.c:14
        a = {4, 1, 2, 1, 8}
        i = <value optimized out>

Jak widzicie low zmienna wyszła poza granicę:

(gdb) p low
$5 = 5

2. Narzędzia do analizy statycznej

$ splint -retvalint -exportlocal qsort.c 
Splint 3.1.2 --- 07 Feb 2011

Finished checking --- no warnings

$ cppcheck qsort.c 
Checking qsort.c...

3. Valgrind z --tool=exp-sgcheck

$ valgrind --tool=exp-sgcheck ./a.out 
==5480== exp-sgcheck, a stack and global array overrun detector
==5480== NOTE: This is an Experimental-Class Valgrind Tool
==5480== Copyright (C) 2003-2012, and GNU GPL'd, by OpenWorks Ltd et al.
==5480== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==5480== Command: ./a.out
==5480== 
==5480== Invalid read of size 4
==5480==    at 0x4005A0: split (qsort.c:46)
==5480==    by 0x4005DE: quicksort (qsort.c:30)
==5480==    by 0x400655: main (qsort.c:14)
==5480==  Address 0x7ff000114 expected vs actual:
==5480==  Expected: stack array "a" of size 20 in frame 2 back from here
==5480==  Actual:   unknown
==5480==  Actual:   is 0 after Expected
==5480== 
After sort: 1 1 2 4 8
==5480== 
==5480== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Lokalizacja at 0x4005A0: split (qsort.c:46) pasuje do tego samego miejsca, w którym znalazłem gdb ręcznie.


16
2018-06-18 11:25


pochodzenie


Zwykle polegam na valgrind do debugowania problemów z pamięcią. - Pavel
w tym może pomóc również ogrodzenie elektryczne (-lefence) - Will
Valgrind jest niezwykle pomocny w dynamicznej pamięci (jestem prawie pewny, że gwarantuje, że znajdzie tu każdą nielegalną operację pamięci), ale ze stosem nie jest to tak oczywiste. Mimo to myślę, że jest to najlepsze dostępne narzędzie, chociaż nie zawsze będzie to miało problem. gcc„s -fstack-protector-all czasami pomagają, za niewielką opłatą. - keltar
Dzięki keltar. Znalazłem Dokumentacja Valgrind dla tablic stosów muszę użyć exp-sgcheck, który wciąż jest eksperymentalny. Wiem, że C nie oferuje sprawdzania związanym z tablicą, ponadto po przekazaniu tablicy do funkcji sizeof informacje są tracone, więc nie jest to łatwe do wyśledzenia. Poza tym uważałem, że narzędzia analizy kodu statycznego również mogą być użyteczne. - Grzegorz Szpetkowski


Odpowiedzi:


Jaki jest zalecany sposób upewnienia się, że każdy dostęp lub zapis do tablicy (przydzielony na stosie) jest rzeczywiście ważny (tj. Nie powodujący nieokreślonego zachowania)?

Co, jeśli użyjesz clang w systemie Linux z opcjami -fsanitize=addressi -fsanitize=undefined? Jest również dostępny w gcc: http://gcc.gnu.org/gcc-4.8/changes.html.


clang z opcją -fsanitize=undefined

To jest przykład:

#include <stdlib.h>

#define N 5

int main(int argc, char *argv[])
{
  int a[N] = {8, 1, 2, 3, 4}, i;

  int r =0;
  int end = atoi(argv[1]);
  for (int i = 0; i != end; ++i)
    r += a[i];

  return r;
}

Następnie

clang -fno-omit-frame-pointer -fsanitize=undefined -g out_boundary.c -o out_boundary_clang

$ ./out_boundary_clang 5
$ ./out_boundary_clang 6
out_boundary.c:12:10: runtime error: index 5 out of bounds for type 'int [5]'
Illegal instruction (core dumped)

A następnie przeanalizuj plik core

Program terminated with signal 4, Illegal instruction.
#0  main (argc=2, argv=0x7fff3a1c28c8) at out_boundary.c:12
12          r += a[i];
(gdb) p i
$1 = 5


clang z opcją -fsanitize=address 

To jest cytat:

The tool can detect the following types of bugs:

* Out-of-bounds accesses to heap, stack and globals
* Use-after-free
* Use-after-return (to some extent)
* Double-free, invalid free
* Memory leaks (experimental)

clang -fno-omit-frame-pointer -fsanitize=address -g out_boundary.c -o out_boundary_clang

I wtedy:

$ ./out_boundary_clang 6 2>&1 | asan_symbolize.py
=================================================================
==9634==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fff91bb2ad4 at pc 0x459c67 bp 0x7fff91bb2910 sp 0x7fff91bb2908
READ of size 4 at 0x7fff91bb2ad4 thread T0
    #0 0x459c66 in main out_boundary.c:12
    #1 0x3a1d81ed1c in __libc_start_main ??:0
    #2 0x4594ac in _start ??:0
Address 0x7fff91bb2ad4 is located in stack of thread T0 at offset 244 in frame
    #0 0x45957f in main out_boundary.c:6
  This frame has 8 object(s):
    [32, 36) ''
    [96, 100) ''
    [160, 168) ''
    [224, 244) 'a'
    [288, 292) 'i'
    [352, 356) 'r'
    [416, 420) 'end'
    [480, 484) 'i1'
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
Shadow bytes around the buggy address:
  0x10007236e500: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007236e510: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007236e520: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007236e530: 00 00 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1
  0x10007236e540: 04 f4 f4 f4 f2 f2 f2 f2 04 f4 f4 f4 f2 f2 f2 f2
=>0x10007236e550: 00 f4 f4 f4 f2 f2 f2 f2 00 00[04]f4 f2 f2 f2 f2
  0x10007236e560: 04 f4 f4 f4 f2 f2 f2 f2 04 f4 f4 f4 f2 f2 f2 f2
  0x10007236e570: 04 f4 f4 f4 f2 f2 f2 f2 04 f4 f4 f4 f3 f3 f3 f3
  0x10007236e580: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007236e590: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007236e5a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:     fa
  Heap right redzone:    fb
  Freed heap region:     fd
  Stack left redzone:    f1
  Stack mid redzone:     f2
  Stack right redzone:   f3
  Stack partial redzone: f4
  Stack after return:    f5
  Stack use after scope: f8
  Global redzone:        f9
  Global init order:     f6
  Poisoned by user:      f7
  ASan internal:         fe
==9634==ABORTING

Lub możesz użyć obu tych opcji. Przydatne linki:


13
2018-06-18 14:13



@skwllsp: -fsanitize=addressi-fsanitize=undefinednie jest włączone na cygwin, który używa gcc 5.2.0 jako czasu pisania. Nie można jej włączyć, ponieważ nie wiem, czy pobierać i kompilować libasan i libusan. - user2284570
Uwaga z gcc musisz połączyć z libasanem, np. gcc -fsanitize=address myprog.c -o myprog -lasan - mondaugen