Proiecte: testare, analiză şi depanare de software

Caut să lucrez la aceste proiecte pe termen lung cu studenţi începând din anii mici, sau eventual diplomanzi. Pe subiecte mai complexe pot lucra şi cu masteranzi începând din primul an. Principalele condiţii necesare sunt interesul, buna înţelegere a problemei abordate şi disponibilitatea de timp.

Pentru practica de vară, teme posibile sunt studii şi implementări preliminare pentru proiectele de mai jos, sau proiecte de dimensiuni mai mici legate de programe şi infrastructuri existente de testarea, analiză şi depanare de software, pentru a învăţa folosirea lor, a le evalua pe programe tipice, sau a scrie module de extensie.

Generare automată de teste

O metodă de a evalua cât de bine e testat un program e de a măsura acoperirea codului prin teste. Criteriile cele mai simple (acoperirea fiecărei linii şi a fiecărei ramificaţii) sunt insuficient de puternice pentru detectarea multor tipuri de erori. E necesară deci:

folosirea unor criterii de acoperire mai precise, care reflectă mai bine funcţionalitatea codului analizat
generarea automată a unor teste cât mai relevante, care să maximizeze acoperirea după criteriile selectate

Modul Visual Studio pentru analiza acoperirii după fluxul de date (dataflow coverage) în programe C#.
Acest criteriu de acoperire corelează utilizările unei variabile cu locurile anterioare de definiţie (atribuire) care dau posibilele ei valori (vezi un articol care studiază problema). Scopul e de a măsura calitatea acoperirii acestui criteriu, şi, în pasul următor, a genera automat teste care acoperă căile încă netestate. Un proiect de licenţă anterior a tratat această problemă pentru Java folosind sistemul de verificare Java PathFinder. Alt proiect a măsurat acoperirea liniilor de cod şi ramificaţiilor folosind infrastructura de analiză Phoenix de la Microsoft.
Testare cu acoperire bazată pe predicate (limbaj la alegere: Java, C#, C, ...)
O bună suită de teste parcurge programul testat pe toate ramurile. Însă ramificaţiile unui program nu sunt independente: comportamentul pe o ramură poate depinde de calea aleasă într-o porţiune anterioară a codului (care a setat un fanion sau a făcut alte atribuiri relevante). Noţiunea de acoperire bazată pe predicate (predicate coverage) exprimă acest aspect, evaluând la fiecare punct în program corelarea dintre condiţii (predicate) considerate relevante. Proiectul va evalua acoperirea unei suite de teste, în raport cu predicate definite de utilizator sau selectate prin analiza codului, şi va genera teste suplimentare pentru cazurile neacoperite.
Testarea bazată pe metrici de corelare obiectuală
Pentru programe şi biblioteci orientate pe obiecte, testele conţin secvenţe de apeluri de metode. Cum numărul de secvenţe posibile creşte exponenţial cu numărul de apeluri, e important ca ele să fie alese judicios. Similar cu acoperirea bazată pe flux de date, proiectul va defini criterii de generare a testelor bazate pe corelarea între metode (de ex. combinarea apelurilor la metode tip getter cu cele de tip setter pentru aceiaşi membri de date; gruparea în teste a metodelor care interacţionează, etc.
Testarea ierarhiilor de clase
Programele orientate pe obiecte pot avea tipuri de erori specifice, datorate polimorfismului (apelul unei metode din altă clasă decât se intenţionează), sau cuplajului între metode care accesează aceiaşi membri de date. Pornind de la modele de eroare cunoscute, proiectul va continua analiza lor şi va genera suite de teste adaptate la detectarea acestor tipuri de erori.

Execuţie simbolică

Când raţionăm despre diversele cazuri în execuţia unui program, adesea nu ne interesează valorile concrete ale unor variabile, ci doar relaţiile în care se află (avem x - y > 0 ? sau a[i] <= a[j] ?). Astfel, nu executăm programul pe valori numerice concrete, ci substituim simboluri şi expresii, ca în matematică, pâstrând pe parcurs relaţiile relevante între acestea. Execuţia

Execuţie simbolică cu Java PathFinder pentru tipuri de date complexe
Pentru tipuri de date numerice, execuţia simbolică e relativ simplă conceptual, şi necesită prelucrarea de relaţii (ecuaţii, inecuaţii) matematice. Mai dificilă e implementarea unor abstracţii potrivite pentru tipuri de date complexe: şiruri de caractere, tablouri, obiecte care conţin la rândul lor obiecte. Se va extinde la tipuri de date mai complexe execuţia simbolică din Java PathFinder, unul din cele mai cunoscute sisteme de verificare pentru programe Java, care implementează o maşină virtuală proprie pentru Java.

Execuţie simbolică înapoi cu Java PathFinder
Sistemul Java Pathfinder implementează execuţia simbolică înainte, pornind de la un apel de metodă specificat de utilizator. De interes e însă şi execuţia simbolică înapoi, de la un punct relevant (de exemplu, de eroare) în care a ajuns programul, pentru a obţine condiţiile care au determinat atingerea acelui punct. Execuţia simbolică înapoi poate fi folosită apoi la depanarea programelor.

Evaluarea sistemului Klee de detectie de erori prin execuţie simbolică
Klee e un sistem recent care detectează erori în programe prin execuţie simbolică direcţionată fie aleator, fie bazat pe diverse criterii (vezi şi acest articol). Scopul proiectului e de a evalua performanţa detecţiei erorilor pe programe de dimensiuni realiste, şi de a propune extensii şi optimizări.

Depanare automată

Odată detectată o execuţie eronată în program, e importantă localizarea cu un grad cât mai mare de automatizare a cauzei erorii, şi corectarea ei. Diverse abordări de succes se bazează fie pe comparaţia directă între o execuţie corectă şi una eronată (delta debugging), sau analiză statistică a unui număr mare de execuţii

Depanare ierarhică şi bazată pe componente
O abordare naturală pentru localizarea erorilor este cea ierarhică, privind execuţia programului la diverse nivele de detalii (v. un articol) relevant. Asemănător, putem aborda depanarea într-un sistem format din componente, efectuând întâi întâi interacţiunile la interfaţa dintre componente, pentru a detecta eventualele erori de interacţiune -- sau, în absenţa acestora, a localiza eroarea în interiorul uneia din componente.
Depanare prin analiză statistică a execuţiilor
Analiza statistică a unui număr mare de execuţii poate da indicii asupra locurilor din cod suspecte de eroare (v. următorul articol). Proiectul va analiza o bază de programe benchmark cu erori cunoscute, urmând ca pe baza rezultatelor să continue dezvoltarea unei metode de localizare a erorilor, posibil bazat pe învăţarea unui model de funcţionare corectă/eronată a programului.
Depanare pornind de la structura fişierelor prelucrate
O categorie de programe sunt cele care prelucrează fişiere, de exemplu documente în diverse formate, pentru vizualizare. Proiectul îşi propune să uşureze depanarea erorilor din acest tip de programe abordând problema în pornind de la structura (cunoscută sau dedusă prin analiză) a fişierelor prelucrate, şi corelând execuţia programului cu prelucrarea realizată în fişier.
Depanarea interacţiunilor între programe complexe
Aţi întâlnit probabil situaţii în care un program (de exemplu un editor de texte, sau un browser) se termină printr-o eroare, provocând în lanţ o eroare fatală în mediul grafic de rulare (server X/window manager). Proiectul va aborda localizarea erorii, prin monitorizarea interacţiunii între programe.

Analiză statică

Proiectele din această categorie urmăresc detectarea unor erori sau extragerea unor informaţii despre funcţionarea programului prin analiza codului sursă, fără rularea efectivă a programului.

Detectarea pierderilor de memorie
Un proiect anterior detectează pierderi de memorie în programe C/C++ folosind infrastructura LLVM. Analiza este însă aproximativă, găsind potenţiale căi de execuţie eronate (pe care nu se face o dealocare sau se face o dublă dealocare), dar nu verifică dacă programul poate într-adevăr urma calea găsită. Pentru aceasta, trebuie reţinute condiţiile la fiecare ramificare de pe cale, şi verificat dacă ele pot fi adevărate simultan. Se va folosi un modul deja existent de reprezentare a condiţiilor, şi biblioteci care verifică dacă ele pot fi adevărate. Analiza trebuie să fie interprocedurală, adică să analizeze programul în totalitate, ţinând cont de efectele care apar la apelurile de proceduri prin transmiterea de parametri şi returnarea de rezultate.
Determinarea sumarelor şi contractelor la nivel de procedură
Cum programele sunt modulare, analiza corectitudinii lor trebuie să ţină cont de aceasta. Informaţii despre cum se leagă rezultatele funcţiilor de parametri acestora sunt necesare, fie că e vorba de detectarea de pierderi de memorie sau de accese invalide, etc. Proiectul va implementa şi eventual extinde algoritmi care calculează astfel de relaţii care rezumă efectul unei funcţii (procedure summaries), în scopul folosirii în analize interprocedurale.
Analiza acceselor la tablouri pentru paralelizare
Pentru execuţia performantă a codului, parcurgerile tablouri de dimensiuni mari se pot paraleliza, alocând un fragment de tablou fiecărei unităţi de procesare. Pentru ca transformarea să fie corectă, la prelucrare nu trebuie să existe interferenţe între fragmente: iteraţia trebuie să avanseze uniform de la un element a altul, iar elementele să nu aibă zone de memorie comune. Folosind o infrastructură de analiză pentru Java (de exemplu Wala de la IBM, se va realiza o analiză care identifică astfel de prelucrări "bine structurate" într-un program.
Determinarea de invarianţi pentru cicluri
Scrierea corectă a programelor este dificilă datorită ciclurilor, unde pot apărea uşor erori. Invarianţii, proprietăţi care se păstrează la fiecare iteraţie au un rol cheie în verificarea programelor. Pentru diverse tipuri de cicluri simple se pot stabili matematic invarianţi, şi se pot determina formule pentru calculul valorilor la sfârşitul ciclului. Infrastructura LLVM implementează astfel de algoritmi în modulul ScalarEvolution. Proiectul va extinde acest modul cu alte tipuri de invarianţi polinomiali trataţi în literatură, pentru a permite verificarea unor programe mai complexe.
Simplificarea programelor prin slicing
La analiza unui program -- pentru depanare, înţelegere sau testare, dorim să urmărim doar porţiunile relevante. Aceasta se realizează prin slicing, determinarea acelor instrucţiuni din program care vor fi afectate de valoarea din punctul curent (forward slicing) sau reciproc, a celor care ar fi putut cauza valoarea curentă (backward slicing). În ciuda utilităţii, există puţine infrastructuri public disponibile pentru slicing. Scopul proiectului e de a realiza un modul de slicing pentru o infrastructură existentă de analiză de cod (C sau Java), pentru a putea fi apoi folosită la depanare.

Infrastructuri de analiză

O listă de infrastructuri reprezentative pentru analiză, detecţie de erori şi testare, care pot fi folosite în aceste proiecte sau altele similare:

CIL: infrastructură de analiză pentru C, scrisă în ML (dialectul OCaml, funcţional/orientat pe obiecte), cu multe facilităţi pentru scrierea de analize la nivel înalt
LLVM, infrastructură de compilare şi analiză pentru C/C++ bazată pe o reprezentare de nivel scăzut, cu maturitate şi performanţe la nivel industrial.
Java PathFinder. Sistem de verificare bazat pe o maşină virtuală Java proprie.
Soot o infrastructură de analiză pentru bytecode Java
Wala o infrastructură de analiză pentru bytecode Java, dezvoltată la IBM
Key, un sistem pentru demonstrarea corectitudinii programelor Java
Why, un alt sistem de verificare deductivă de programe C sau Java
Phoenix, o infrastructură de analiză şi compilare pentru platforma .NET (Microsoft)
PEX, o infrastructură de generare automată de teste pentru platforma .NET (Microsoft)
CHESS, un sistem de detectare a erorilor in programe concurente (Microsoft)

Last modified: Thu Jun 18 17:00:00 EEST 2009