Erlang programok statikus elemzése és szeletelése

Bozó, István

Erlang programok statikus elemzése és szeletelése

Date: 2018

Subject: Műszaki tudományok/Informatikai tudományok
Erlang
static analysis
control flow analysis
control flow graph
execution path
postdominator analysis
control dependence graph
program slicing
test case selection
impact analysis
communication model
process identification
hidden dependencies
server analysis
Informatika D. I./Az informatika alapjai és módszerei.
Erlang
statikus elemzés
vezérlésfolyam elemzés
vezérlésfolyam-gráf
végrehajtási út
posztdominátor elemzés
vezérlésfüggőségi gráf
programszeletelés
tesztesetszelekció
hatáselemzés
kommunikációs modell
folyamatok azonosítása
rejtett függőség
szerverek elemzése

URI: http://hdl.handle.net/10831/40600

Link to Library Catalogue: https://opac.elte.hu/Record/opac-EUL01-961778

MTMT: 30548227

DOI: 10.15476/ELTE.2018.169

Abstract:

A funkcionális programozási nyelvek terjedésének velejárója, hogy felmerül az igény olyan eszközökre, amelyek a fejlesztési folyamatot támogatják. Ezek lehetnek futási idejű eszközök, vagy olyanok, melyek csupán a forráskód elemzésével kı́nálnak hasznos információkat a fejlesztők számára.

Az Erlang ipari környezetben is gyakran használt funkcionális programozási nyelv. A RefactorErl egy statikus elemző és refaktoráló eszköz Erlanghoz, mely számos transzformációt biztosı́t a forráskód jelentésmegőrző átalakı́tására, másrészről kiterjedt statikus elemzőkészlettel segı́ti a fejlesztőket a mindennapos tevékenységükben.

Kutatásomban olyan elemzési módszerekkel foglalkoztam, amelyek segı́tségével az Erlang programok forráskódjában rejlő összetett összefüggések nyerhetők ki. Ezek az eredmények pedig további magasabb szintű elemzések alapját képzik. Az ismertetett eredményeim a vezérlés és az Erlang folyamatok közötti kapcsolatok elemzéséhez kapcsolódnak.

A dolgozatomban Erlang programok vezérlésfolyam-gráfját adtam meg, amely tartalmazza a programok végrehajtása során előálló lehetséges végrehajtási utakat. A gráfot a nyelv szintaktikus kategóriáihoz rendelt formális szabályok segı́tségével definiáltam, amelyek a nyelv szemantikájának megfelelően adják meg a vezérlésfolyam-gráf éleit. A vezérlésfolyam-gráf felhasználásra került további elemzésekhez is, mint például a párhuzamosı́tható komponensek azonosı́tása.

A vezérlésfolyam-gráf, illetve a benne foglalt információk felhasználhatóak a forráskódban történő változások hatáselemzéséhez. A vezérlésfüggőségi gráf egy kompaktabb reprezentáció, amely a vezérlési utakban lévő szekvenciák eliminálásával már csak a kifejezések közötti közvetlen függőségeket tartalmazza. Megadtam Erlang programokra a vezérlésfüggőségi gráfot, amelyet
adatfüggőségi információkkal egészı́tettem ki. Az ı́gy definiált Erlang függőségi gráf felhasználható gráf alapú statikus programszeleteléshez. A definiált infrastruktúrára épı́tve megadtam egy hatáselemzés alapú teszteset szelekciós módszert. A módszer azon tesztesetek halmazát adja meg, amelyek érintettek lehetnek a változtatás/transzformáció kapcsán. Azaz a változtatás hatása elterjedhet a tesztelt funkcionalitásba. Az elemzés nem csak a transzformációk hatásának elemzésére, hanem tetszőleges változás elemzésére is használható.

Dolgozatomban bemutattam Erlang programok egy statikus kommunikációs modelljét. Megadtam azokat az algoritmusokat, melyek segı́tségével felderı́thetőek az elindı́tott Erlang folyamatok és a köztük aszinkron üzenetküldésekkel lebonyolı́tott kommunikáció. A modellbe felvettem olyan rejtett kommunikációs elemeket is, mint a közös osztott memóriának tekinthető Erlang Term Storage (ets) táblák használata. Megadtam azokat a statikus elemzési algoritmusokat, melyek felhasználásával kiegészı́thető a kommunikációs gráf speciális Erlang folyamatokkal (például generikus szerverek) és az interfészeiken keresztül történő rejtett kommunikációval. A kommunikációs gráf kiválóan használható a kódban rejlő összefüggések megjelenı́tésére, kódmegértés, konkurenciából fakadó hibakeresés támogatásához. Ugyanakkor felhasználható konkurens programok változásához köthető hatáselemzés pontosı́tásához is.

Abstract:

Functional programming languages are getting more popular nowadays, thus there is a high demand on new tools that may support the development process. There are two main types of such tools, one is operating with dynamic information by running the code, the other is performing static analysis on the source code of the program. Erlang is a functional programming language designed for developing real world applications. The RefactorErl tool is an extensive static analyzer framework developed for Erlang. The tool offers several refactorings and code comprehension support for developers. In general, the focus of my research was to develop new static analysis methods. These methods extract compound semantic information from the source code, and the result could be used for other analysis methods. My results are related to control flow, control dependence, impact analysis and communication model of Erlang programs. In my dissertation, I have presented formal control flow rules based on the semantics of the language. The rules are compositional and can be used for developing control flow graph of an expression, or a function. The results of the control flow graph have been used further analysis techniques, like discovering parallelable components in legacy source codes. The information available in the control flow graphs can be used in many ways. It can be used for parallelization, debugging or change impact analysis. The control dependence graph is a more compact representation compared to control flow graph. It includes only direct control dependencies, while the control flow graph contains every execution path of a program. I have presented and extended the control dependence graph with data dependencies, what we call Erlang dependence graph. I have presented an impact analysis method based on the dependence graph. This method can be used for relevant test case selection. It selects only those test cases that could be affected by a change. The presented method can not only be used for impact analysis of refactorings, but can be generalized for an arbitrary modification. I have also presented a method for extracting the communication model from Erlang source codes. I have described the algorithms that can be used to identify the processes and the possible communication between them. I have extended the model with the analysis results of hidden communication. The Erlang Term Storage (ets) tables can be used as shared memory between processes. Any reading or writing operation is taken as an interaction with other processes accessing the same table. I have added analysis of generic server behaviors as another extension to the process model. This introduces another type processes and the hidden communication. The results can be used in code comprehension techniques, but the results from the communication model could be used in impact analysis as well.

Show full item record