Hunting Bugs with Coccinelle – Københavns Universitet

Hunting Bugs with Coccinelle

Software bugs are an ever increasing liability as we become more dependent on software. While many solutions have been produced to find bugs, there is still ample room for improvement. In this thesis we have used the source-to-source transformation engine for the C programming language, Coccinelle, by extending it with reporting facilities and static analysis prototyping capabilities using Python that integrate with the OCaml code of Coccinelle. Using the prototyping capabilities, we have developed patterns for matching stack-based buffer overflows and use-after-free bugs. We have furthermore developed an alternative control flow graph representation for Coccinelle in an effort to decrease the number of false positives when we search for use-after-free bugs, and we have implemented a generalised constant propagation algorithm to estimate value ranges for program variables. We have run our bug patterns on several code-bases ranging from 30,000 lines of source code up to over 5.5 million lines of source code and found bugs in all of the code-bases. While our patterns only provide a first step towards making Coccinelle into a general-purpose bug hunting tool, they have successfully shown that Coccinelle has the potential to compete with many of the currently available bug finding tools.

I takt med at vi bliver mere afhængige af software jo større et problem bliver programfejl. Selvom der er lavet mange løsninger til at finde programfejl, så er der stadig rig mulighed for at lave forbedringer. Vi har benyttet Coccinelle, et kildeteksttransformeringsprogram til C-programmeringssproget, og udvidet det med funktionalitet til at rapportere fejl og med funktionalitet til at prototype statiske analyser ved at integrere Python med den eksisterende OCaml-kode som Coccinelle er skrevet i. Ved at bruge prototype-funktionaliteterne har vi udviklet søgemønstre til at finde stak-baserede buffer-overløb og use-after-free-fejl. Vi har ydermere udviklet en alternativ repræsentation af control flow graphs i Coccinelle for at begrænse antallet af falske positiver ved søgning efter use-after-free fejl, og vi har implementeret generalised constant propagation til at beregne de mulige værdier en program-variabel kan have på kørselstidspunktet. Vi har afviklet vores søgemønstre på kildetekster til flere programmer som indeholder fra 30.000 linjers kildetekst til over 5,5 millioner linjers kildetekst, og vi har fundet fejl i samtlige programmer. Selvom vores søgemønstre kun er det første skridt til at bruge Coccinelle som et generelt anvendeligt fejlfindingsværktøj, så har de vist, at Coccinelle har potentiale til at konkurrere på lige fod med mange af de fejlfindingsværktøjer som er tilgængelige i dag.