In this thesis we address the problem of control flow reconstruction in the presence of indirect jumps. We introduce an alternating approach which combines both overand under-approximation to increase the precision of the reconstructed control flow automaton compared to pure over-approximation. More specifically, the abstract interpretation based tool, Jakstab, from earlier work by Kinder, is used for the over-approximation. Furthermore, directed symbolic execution is applied to under-approximate successors of instructions when these can not be over-approximated precisely. The results of our experiments show that our approach can improve the precision of the reconstructed CFA compared to only using Jakstab. However, they reveal that our approach consumes a large amount of memory since it requires extraction and temporary storage of a large number of possible paths to the unresolved locations. As such, its usability is limited to control flow automatas of limited complexity. Further, the results show that strided interval analysis suffers in performance when encountering particularly challenging loops in the control flow automaton. / I detta examensarbete studeras hur rekonstruktion av kontrollflöde kan utföras i närvaro av indirekta hoppinstruktioner. I examensarbetet introduceras ett alternerande tillvägagångssätt som kombinerar både överoch underapproximation för att öka precisionen av den rekonstruerade kontrollflödesautomaten jämfört med endast överapproximation. Mer specifikt används det abstrakta tolknings-baserade verktyget, Jakstab, tidigare utvecklat av Kinder, för överapproximation. Vidare nyttjas riktad symbolisk exekvering för att underapproximera efterträdare till instruktioner när dessa inte kunnat överapproximeras med hög precision. Resultaten av våra experiment visar att vårt tillvägagångssätt kan förbättra precisionen hos den rekonstruerade kontrollflödesautomaten jämfört med att endast använda Jakstab. Dock visar de att vårt tillvägagångssätt kan fordra en stor mängd minne då det kräver extraktion och tillfällig lagring av ett stort antal möjliga vandringar från programmets ingång till de olösta programpositionerna. Därmed är dess användbarhet limiterad till kontrollflödesautomater av begränsad complexitet. Vidare visar resultaten av våra experiment även att analyser baserade på klivande intervaller tappar i prestanda när de möter en vis typ av loopar i kontrollflödesautomaten.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-271208 |
| Date | January 2019 |
| Creators | Peterson, Thomas |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2019:835 |
Page generated in 0.0028 seconds