Tehnike dinamičke analize za otkrivanje grešaka u strukturama podataka bez zaključavanja

master's thesis

• Title (english): Dynamic analysis techniques for detecting errors in lock-free data structures
• Author: Gabriel Marinković
• Mentor: Ante Đerek (mentor)
• Committee member: Ante Đerek (predsjednik povjerenstva)
• Committee member: Klemo Vladimir (član povjerenstva)
• Committee member: Adrian Satja Kurdija (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-02, Croatia

Abstract

Testiranje višedretvenih lock-free algoritama predstavlja veliki problem zbog nedeterminističke prirode greški koje mogu ovisiti o vremenskom rasporedu dretvi. U ovom radu predstavljamo sustav kojim je moguće sistematski izvršiti sve moguće vremenske rasporede dretvi koje mogu dovesti do greške. U slučaju pronađene greške moguće je pouzdano reproducirati raspored dretvi koji ju izaziva. Sustav koristi dinamičku instrumentaciju strojnog koda kako bi drastično smanjio broj rasporeda dretvi koje treba testirati. Najveća postignuća našeg sustava naspram postojećih rješenja su mogućnost testiranja postojećih algoritama bez potrebe za izmjenom izvornog koda i mogućnost testiranja visoko-optimiziranih izvršnih datoteka. Koristeći naš sustav evaluirali smo i provjerili ispravan rad nekoliko popularnih javno dostupnih biblioteka sa lock-free strukturama podataka.

Abstract (english)

Automated testing of multithreaded lock-free algorithms poses a significant challenge due to the possibility of bugs whose appearance depends on the scheduling of threads. In this thesis we present a novel system for systematic testing of all possible thread scheduling orders which might impact the program’s final result. Discovered bugs can be reliably reproduced with the same thread schedule. The most significant improvement of our system compared to previous methods is the ability to test existing code without any modifications to its source, and the ability to test their highly optimized builds. We used our system to evaluate and check the correctness of several popular publicly available libraries of lock-free data structures.

• Keywords: automatsko testiranje; konflikt istovremenog pristupa; dinaimčna instrumentacija; višedretvenost
• Keywords (english): automatic testing; race conditions; dynamic binary instrumentation; multithreading
• Language: croatian
• URN:NBN: urn:nbn:hr:168:879504
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-10-12 21:27:12