English version  


CNCSIS

Modulul ECHOS++

Redenumit SAFE+

3.1 Definirea unui model pentru stocarea rezultatelor analizei

In cadrul primei faze a proiectului (2007) am experimentat cu infrastructura de analiza statica Oink (http://www.cubewano.org/oink). In urma activitatii de integrare a acestei inftrastructurii in Eclipse, am realizat ca Oink are cateva neajunsuri care ingreuneaza dezvoltarea altor analize statice. Faptul ca graful fluxului de control nu reflecta intotdeauna codul sursa si maturitatea insuficienta a infrastructurii au condus la decizia de a alege si folosi alta infrastructura pentru dezvoltarea analizelor statice pentru C/C++.

Infrastructura de analiza statica aleasa este cea oferita de cadrul de compilare LLVM (http://www.llvm.org). LLVM este un compilator proiectat pentru optimizarea programelor care ofera un limbaj intermediar de reprezentare a codului cu instructiuni si sistem de tipuri independent de arhitectura sau limbajul de programare.

Rezultatele analizelor sunt modelate prin obiecte ce reprezinta secvente din caile posibile de executie prin programe (vezi exemplu de mai jos). Schimbul de date intre infrastructura de analiza si mediul integrat de dezvoltare se face prin serializarea/deserializarea rezultatelor intr-un / dintr-un fisier predefinit.

3.2 si 3.3 Analiza scalabila de pointeri folosind nivele succesive de analiza si rafinare prin partitionare si Detectie de pierderi de memorie in C++ folosind analize la cerere.

Pentru a identifica alocarea defectuoasa a memoriei in progamele C/C++ am dezvoltat o analiza similara cu cea expusa in [1]. Algoritmul se bazeaza pe identificarea cailor din graful de flux de control care unesc o alocare de memorie cu o eliberare de memorie. Avand aceste cai, identificarea pierderilor de memorie se rezuma la filtrarea cailor care contin doar alocare fara eliberare sau doar eliberare fara alocare de memorie.

Aceasta abordare nu se rezuma doar la identificarea programelor care pot avea pierderi de memorie, chiar mai mult, furnizeaza si informatii legate de conditiile care trebuie indeplinite pentru ca programul sa piarda memorie.

De exemplu, in figura de mai jos este prezentat graful de flux de control pentru o functia simpla example() care in anumite conditii pierde memorie.

Algoritmul pentru identificarea pierderilor de memorie este urmatorul: Pasul 1, identificarea cailor prin graful fluxului de control care incep cu instructiunea de alocare.Acestea sunt: {B1, B2, B4} si {B1, B3, B4} pentru cazurile in care C este adevarat, respectiv fals. Pasul 2, identificarea cailor care nu contin istructiunea de eliberare a memoriei. In acest caz calea care contine doar alocare fara eliberare este {B1, B3, B4}. Pasul 3, identificarea cailor care contin doar instructiuni de eliberare a memoriei fara instructiuni de alocare. Exemplul de mai jos nu contine astfel de cai.

Caile identificate in pasii doi si trei reprezinta cazurile de alocare defectuasa a memoriei. Unele din defectele identificate la pasul doi pot fi corectate automat, in exemplul de mai jos, inserarea instructiunii free(X) dupa instructiunile din blocul B3 corecteaza defectul de alocare.


Figura 3.3.1 - Pierdere de memorie intr-o functie C/C++

Este important de mentionat ca in programe apare deseori cazul in care o zona de memorie este referita de mai multe variabile, identificarea tuturor variabilelor din program care refera o anumita zona de memorie se numeste analiza aliasurilor referintelor de memorie (points-to analysis).

Precizia analizei de identificarea pierderilor de memorie implementata de noi este strans legata de precizia cu care se identifica aliasurile referintelor de memorie.

Noua infrastructura, LLVM (http://www.llvm.org) dispune de multipli algoritmi de identificare a aliasurilor referintelor de memorie cu diverse precizii. Utilizarea acestora a accelerat mult dezvoltarea analizei de identificare a pierderilor de memorie. LLVM, fiind o infrastructura de compilare, poate fi usor folosita in cadrul mediului integrat pentru dezvoltare ca si compilator dedicat analizelor. Acest concept se muleaza foarte bine pe stilul de lucru Eclipse bazat pe "moduri de lucru" (modul dezvoltare, modul depanare etc).

Analiza dezvoltata poate identifica pierderile de memorie ce apar in cadrul aceleasi functii (este intraprocedurala), caracteristica ce confera eficienta din punct de vedere al utilizarii memoriei (de dorit in cazul analizei programelor de mari dimensiuni) dar implica si o precizie redusa, analiza identificand multe tinte false.

Pentru a imbunatatirea preciziei, va trebui, pe de-o parte, sa extindem scopul analizei astfel incat sa urmarim apleurile de functii (analiza sa devina interprocedurala), iar pe de alta parte va trebui sa dezvoltam un algoritm de filtrare a rezultatelor bazat pe demonstrarea viabilitatii unor cai oarecare din program.

In privinta integrarii in mediul Eclipse, munca noastra se concentreaza pe extinderea modului de lucru "dezvoltare" cu elemente grafice care sa evidentieze alocarea defectuoasa a memoriei (buline de avertizare, sublinierea codului etc). Odata dezvoltat acest cadru de afisarea a rezultatelor, il vom folosi si pentru celelalte analize (dereferentieri invalide, depasiri de indici etc).

Extragerea rezultatelor din infrastructura de analiza bazata pe LLVM se poate face usor datorita faptului ca LLVM poate fi folosit in Eclipse pe post de compilator, astfel programatorul va avea la dispozitie, compilatorul standard pentru generarea codului de productie si compilatorul LLVM (cu analizele noastre integrate) pentru identificarea erorilor in cod.

[1] Sigmund Cherem, Lonnie Princehouse, Radu Rugina. Practical Memory Leak Detection using Guarded Value-Flow Analysis. SIGPLAN Notices, Volume 42, Issue 6 (June 2007), pp. 480-491.

Ultima actualizare: 11 Mai, 2010