Arbetet har undersökt hur predikatbaserad exekvering, i form av ARM-arkitekturens stöd för villkorlig exekvering, fungerar som optimering av specifika implementationer av if- och if-else-satser i ARM-maskinkod. Som en del av arbetet implementerades en för ändamålet konstruerad optimeringsalgoritm som optimerar if- och if-else-satser med hjälp av predikatbaserad exekvering, vilken användes för att kunna utföra de mätningar som ligger till grund för resultatet. Fokus låg på den skillnad i kodstorlek och/eller tidseffektivitet som optimeringen gav upphov till. Resultatet tyder på att predikatbaserad exekvering använd som optimering kan leda till vissa vinster i kodstorlek (direkt beroende på antalet if-/if-else-satser) och lite större vinster i tidseffektivitet (beroende på hur stora if-/if-else-satserna är, samt hur ofta de exekveras).

One of the more promising solutions for automated binary testing today is hybrid fuzzing, a combination of the two acknowledged approaches, fuzzing and symbolic execution, for detecting errors in code. Hybrid fuzzing is one of the pioneering works coming from the authors of Angr and Driller, opening up for the possibility for more specialized tools such as QSYM to come forth. These hybrid fuzzers are coverage guided, meaning they measure their success in how much code they have covered. This is a typical approach but, as with many, it is not flawless. Just because a region of code has been covered does not mean it has been fully tested. Some flaws depend on the context in which the code is being executed, such as double-free vulnerabilities. Even if the free routine has been invoked twice, it does not mean that a double-free bug has occurred. To cause such a vulnerability, one has to free the same memory chunk twice (without it being reallocated between the two invocations to free). In this research, we will extend one of the current state-of-the-art hybrid fuzzers, QSYM, which is an open source project. We do this extension, adding double-free detection, in a tool we call QSIMP. We will then investigate our hypothesis, stating that it is possible to implement such functionality without losing so much performance that it would make the tool impractical. To test our hypothesis we have designed two experiments. One experiment tests the ability of our tool to find double-free bugs (the type of context-sensitive bug that we have chosen to test with). In our second experiment, we explore the scalability of the tool when this functionality is executed. Our experiments showed that we were able to implement context-sensitive bug detection within QSYM. We can find most double-free vulnerabilities we have tested it on, although not all, because of some optimizations that we were unable to build past. This has been done with small effects on scalability according to our tests. Our tool can find the same bugs that the original QSYM while adding functionality to find double-free vulnerabilities. / En av de mer lovande lösningarna för automatiserad binärtestning är i dagsläget hybrid fuzzing, en kombination av två vedertagna tillvägagångssätt, fuzzing och symbolisk exekvering. Forskarna som utvecklade Angr och Driller anses ofta vara några av de första med att testa denna approach. Detta har i sin tur öppnat upp för fler mer specialiserade verktyg som QSYM. Dessa hybrid fuzzers mäter oftast sin framgång i hänsyn till hur mycket kod som nås under testningen. Detta är ett typiskt tillvägagångssätt, men som med många metoder är det inte felfri. Kod som har exekverats, utan att en bugg utlösts, är inte nödvändigtvis felfri. Vissa buggar beror på vilken kontext maskininstruktioner exekveras i -- ett exempel är double-free sårbarheter. Att minne har frigjorts flera gånger betyder inte ovillkorligen att en double-free sårbarhet har uppstått. För att en sådan sårbarhet ska uppstå måste samma minne frigöras flera gånger (utan att detta minne omallokerats mellan anropen till free). I detta projekt breddar vi en av de främsta hybrid fuzzers, QSYM, ett projekt med öppen källkod. Det vi tillför är detektering av double-free i ett verktyg vi kallar QSIMP. Vi undersöker sedan vår hypotes, som säger att det är möjligt att implementera sådan funktionalitet utan att förlora så mycket prestanda att det gör verktyget opraktiskt. För att bepröva hypotesen har vi designat två experiment. Ett experiment testar verktygets förmåga att detektera double-free sårbarheter (den sortens kontext-känsliga sårbarheter vi har valt att fokusera på). I det andra experimentet utforskar vi huruvida verktyget är skalbart då den nya funktionaliteten körs. Våra experiment visar att vi har möjliggjort detektering av kontext-känsliga buggar genom vidareutveckling av verktyget QSYM. QSIMP hittar double-free buggar, dock inte alla, på grund av optimiseringar som vi ej har lyckats arbeta runt. Detta har gjorts utan större effekter på skalbarheten av verktyget enligt resultaten från våra experiment. Vårt verktyg hittar samma buggar som orignal verktyget QSYM, samtidigt som vi tillägger funktionalitet för att hitta double-free sårbarheter.

Utmaningar i modern processortillverkning begränsar klockfrekvensen för enkeltrådiga applikationer, vilket har resulterat i utvecklingen av flerkärniga processorer. Dessa processorer tillåter flertrådig exekvering och ökar därmed prestandan. För att undersöka möjligheterna med parallell exekvering används en Fast Fourier Transform algoritm där trådprestanda mäts för olika skapade tester med varierande problemstorlekar. Dessa tester körs på tre testsystem och använder olika sökalgoritmer för att dynamiskt justera antalet trådar vid exekvering. Denna prestanda jämförs sedan med den högsta möjliga prestanda som kan fås genom Brute-Forcing. Testerna använder OpenMP-instruktioner för att specificera antalet trådar som finns tillgängliga för programexekvering. För mindre problemstorlekar resulterar färre antal trådar i högre prestanda. Motsatsen gäller för större problemstorlekar, där många trådar föredras istället. Denna rapport visar att användning av alla tillgängliga trådar för ett system inte är optimalt i alla lägen då det finns en tydlig koppling mellan problemstorlek och det optimala antalet trådar för maximal prestanda. Detta gäller för alla tre testsystem som omfattas av rapporten. Metodiken som har använts för att skapa testerna har gjort det möjligt att dynamiskt kunna justera antalet trådar vid exekvering. Rapporten visar också att dynamisk justering av antalet trådar inte passar för alla typer av applikationer. / As physical limitations limit the clock frequencies available for a single thread, processor vendors increasingly build multi-core systems with support for dividing processes across multiple threads for increased overall processing power. To examine parallelization capabilities, a fast fourier transform algorithm is used to benchmark parallel execution and compare brute-forced optimum with results from various search algorithms and scenarios across three different testbed systems. These algorithms use OpenMP instructions to directly specify number of threads available for program execution. For smaller problem sizes the tests heavily favour fewer threads, whereas the larger problems favour the native 'maximum' thread count. Several algorithms were used to compare ways of searching for the optimum thread values at runtime. We showed that running at maximum threads is not always the most optimum choice as there is a clear relationship between the problem size and the optimal thread-count in the experimental setup across all three machines. The methods used also made it possible to identify a way to dynamically adjust the thread-count during runtime of the benchmark, however it is not certain all applications would be suitable for this type of dynamic thread assignment

Many online fighting games use rollback netcode in order to compensate for network delay. Rollback netcode allows players to experience the game as having reduced delay. A drawback of this is that players will sometimes see the game quickly ”jump” to a different state to adjust for the the remote player’s actions. Rollback netcode implementations require a method for predicting the remote player’s next button inputs. Current implementations use a naive repeatlastframe policy for such prediction. There is a possibility that alternative methods may lead to improved user experience. This project examines the problem of improving input prediction in fighting games. It details the development of a new prediction model based on recurrent neural networks. The model was trained and evaluated using a dataset of several thousand recorded player input sequences. The results show that the new model slightly outperforms the naive method in prediction accuracy, with the difference being greater for longer predictions. However, it has far higher requirements both in terms of memory and computation cost. It seems unlikely that the model would significantly improve on current rollback netcode implementations. However, there may be ways to improve predictions further, and the effects on user experience remains unknown. / Många online fightingspel använder rollback netcode för att kompensera för nätverksfördröjning. Rollback netcode låter spelare uppleva spelet med mindre fördröjning. En nackdel av detta är att spelare ibland ser spelet snabbt ”hoppa” till ett annat tillstånd för att justera för motspelarens handlingar. Rollback netcode implementationer behöver en policy för att förutsäga motspelarens nästa knapptryckningar. Nuvarande implementationer använder en naiv repetera-senaste-frame policy för förutsägelser. Det finns en möjlighet att alternativa metoder kan leda till förbättrad användarupplevelse. Det här projektet undersöker problemet att förbättra förutsägelser av knapptryckningar i fightingspel. Det beskriver utvecklingen av en ny förutsägelsemodell baserad på rekursiva neuronnät. Modellen tränades och evaluerades med ett dataset av flera tusen inspelade knappsekvenser. Resultaten visar att den nya modellen överträffar den naiva metoden i noggrannhet, med större skillnad för längre förutsägelser. Dock har den mycket högre krav i både minne och beräkningskostad. Det verkar osannolikt att modellen skulle avsevärt förbättra nuvarande rollback netcode implementationer. Men det kan finnas sätt att förbättra förutsägelser ytterligare, och påverkan på användarupplevelsen förblir okänd.

As the number of Internet of Things devices is increasing rapidly, it is of utmost significance that the implementations of protocols for constrained devices are bug-free. In general implementations of network protocols are error-prone due to their complex nature and ambiguities in the protocol specification. Implementations of network protocols often contain critical errors which could be exploited. To avoid bugs and vulnerabilities, the implementation of network protocols has to adhere to their specifications. The objective of this thesis is to use symbolic execution to test one implementation of the Ephemeral Diffie-Hellman Over COSE (EDHOC) protocol and one implementation of the Constrained Application Protocol (CoAP) against their specifications. The goal is to identify bugs such as crashes, non-conformances, memory errors, and security vulnerabilities that may occur if the implementations are not adhering to their specifications. The methodology to do this consists of three steps: 1) extracting requirements from the protocols Request For Comments and expressing them as formulas, 2) preparing the system under test for symbolic execution and applying the formulas during symbolic execution to detect any paths that violate a requirement, 3) for every path which violates a requirement, the concrete value that the symbolic execution engine provided is used in the unmodified implementation to validate the bug. In total seven non-conformances were found which have been reported to developers. One non-conformance was found in the EDHOC implementation and six were found in the CoAP implementation. / Eftersom antalet Internet of Things enheter ökar snabbt är det av yttersta vikt att imple-menteringarna av nätverksprotokoll för Internet of Things enheter är korrekta. Generellt sett är implementeringar av nätverksprotokoll felbenägna på grund av deras komplexa natur och oklarheter i protokollspecifikationen. Implementeringar av nätverksprotokoll innehåller ofta kritiska buggar som kan utnyttjas. För att undvika buggar och sårbarheter måste implementeringar av nätverksprotokoll följa sina specifikationer. Målet med detta examensarbete är att använda symbolisk exekvering för att testa en implementation av protokollet Ephemeral Diffie-Hellman Over COSE ( EDHOC ) och en implementation av protokollet Constrained Application Protocol (CoAP) mot deras specifikationer. Syftet är att identifiera buggar såsom krascher, icke-konformiteter, minnesfel och säker-hetssårbarheter som kan uppstå om implementeringarna inte följer sina specifikationer. Metodiken för att uppnå detta består av tre steg: 1) extrahera krav från protokollensspecifikationer och uttrycka dem som formler, 2) förbereda systemet som ska testas försymbolisk exekvering och tillämpa formlerna under symbolisk exekvering för att upp-täcka eventuella vägar som bryter mot ett krav, 3) för varje väg som bryter mot ett krav används det konkreta värde som den symboliska exekveringsmotorn tillhandahåller i den oförändrade implementationen för att validera buggen. Totalt sett hittades sju icke-konformiteter. En icke-konformitet hittades i EDHOC implementeringen och sex hittades i CoAP implementeringen.

The main objective of this thesis was to develop appropriate strategies and find factors that affect the usability of parameterized designs. This was accomplished by investigate the user-interface and how it is designed to meet the user's information needs. The thesis also embraces the basic theories in terms of investigation, cognitive design principles and human behavior patterns in the interaction with the machine. The approach has led to an explorative investigation in this subject area. The thesis also had the purpose to achieve more efficient ways for development of motor chainsaws at Husqvarna AB's department Global Cutting Equipment. That can be achieved through reduce costs of development per sold unit. To reduce cost depends to what extend the program is helping the user to achieve goals during the design execution. The thesis also includes an investigation of the factors that affect the design of such a program. To explore appropriate strategies was a theoretical design process implemented in the study. From the perspective of technology has the author utilized knowledge in engineering design and programming. The program approach utilized was Visual Basic languish in Visual Studio enviroment for the user-interface and a Catia V5 CAD-platform for the chainsaw design. The result is a program which could use reconfigured parameters as needed to create customized designs correctly and effectively. This thesis has also resulted in appropriate principles for the design of a user-friendly interface that were up for the task to be a supporting tool through the execution. It has also been established appropriate tools and methods for analysis and optimization of the program. The author feels that the results of methods and principles in this study were of high reliability and can therefore be applied to other projects, even if the results only are valid for this specific case. / Huvudsyftet med detta examensarbete har varit att utveckla lämpliga strategier och finna faktorer vilka påverkar användarvänligheten för en parametriserad design. Detta åstadkomms genom att undersöka hur användarformulärets gränssnitt ska utformas för att möta användarens informationsbehov. Examensarbetet omfattar även grundteorier vad gäller undersökningsmetoder, kognitiva designprinciper och människans beteendemönster i interaktion med maskin. Tillvägagångsättet har inneburit en explorativ undersökning i detta ämnesområdet. Examensarbetet har även haft syftet att åstadkomma effektivare utvecklingsprocess av motorsågskedjor för Husqvarna AB’s avdelning Global Cutting Equipment. Detta kan åstadkommas genom minskade kostnader i utveckling per såld enhet. Att reducera kostnader påverkas av vilken omfattning programmet hjälper användaren att uppnå mål under exekveringen. Examensarbetet inkluderar även en undersökning av faktorer vilka påverkar designen i ett sådant program. För att undersöka lämpliga strategier i genomförandet har en teoretisk designprocess använts. Ur tekniskt perspektiv har författaren även använt kunskaper inom konstruktionsdesign och programmering. De använda programmen i genomförandet har varit Visual Basic språk i Visual Studio miljö för användarformuläret och en CAD-plattform i Catia V5 för kedjekonstruktionen. Resultat är ett program vilken skulle kunna omkonstruera designen korrekt och effektivt med parametrar efter behov. Arbetet har även resulterat i lämpliga principer för designen av ett användarvänligt gränssnitt vilken kan klara uppgiften att vara ett hjälpande verktyg under exekveringen. Det har även fastställts en del lämpliga verktyg eller metoder för analys och optimering av programmet. Författaren upplever även att resultaten av metoder och principer i denna studie, var av hög reliabilitet och kan därför appliceras på andra projekt, även om resultaten bara är giltiga för denna specifika studie.

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.