A programszeletelés gyakorlati alkalmazása és használata a szoftver tesztelésben és karbantartásban Doktori értekezés tézisei
Hajnal Ákos Témavezetık:
Forgács István, Ph.D. Varga László Zsolt, Ph.D. Eötvös Loránd Tudományegyetem (ELTE), Informatikai Kar (IK) Informatika doktori iskola (Benczúr András, D.Sc.) Az informatika alapjai és módszertana (Demetrovics János, D.Sc.)
Magyar Tudományos Akadémia Számítástechnikai és Automatizálási Kutatóintézet (MTA SZTAKI)
Budapest, 2012
Bevezetés A COBOL-ra gyakran elavult, alig használt programozási nyelvként gondolnak, pedig napjainkban is több milliárd sornyi COBOL kód fut világszerte, sıt, még mindig ez a leggyakrabban használt programnyelv az üzleti alkalmazásokban. Egy tanulmány szerint 1997-ben a világon futó programkódok 80%-át COBOL-ban írták, a programsorok számát 240 milliárdra becsülték. Jóllehet, a COBOL szerepe csökkent az elmúlt évtizedekben, várhatóan még a következı tíz évben is a COBOL lesz a domináns programozási nyelv [Binkley 2007]. A COBOL alkalmazások általában rendkívül nagyok, méretük gyakran meghaladja az egymillió programsort, de nem szokatlan a tízmillió sornál nagyobb kódméret sem. A napjainkban használt COBOL rendszerek nem ritkán 30−40 évesek, amelyek karbantartása rendkívül munkaigényes és költséges feladat. A naprakész dokumentáció hiánya, a rosszul tervezett logikai struktúra és az eseti hibajavítások tovább nehezítik a késıbbi programkarbantartást. Ráadásul óriási kockázatot rejt ezen programkódok modernizálása, amelyet a cégek általában nem mernek felvállalni. A programszeletelés alkalmazása nagy segítséget nyújthat ezen karbantartási feladatok elvégzésében. Mark Weiser publikálta elıször [1984] a programszeletelés ötletét, amely során a kód azon részeit „távolítjuk el”, amelyeknek igazolhatóan nincs hatása a vizsgált „szemantikai aspektusra”, amelyet szeletelési kritériumnak nevezünk. A programszeletek általában lényegesen kisebbek, mint a teljes programkód, ezért ezek könnyebben megérthetık, vizsgálhatók. A Weiser által bemutatott klasszikus hátramenı statikus programszeletelési technikát számos új szeletelési variáns követte, amilyen például a dinamikus, a kvázi-statikus, a feltételes, a hibrid vagy a lényeges szeletelés. A programszeletelés alkalmazhatóságát a szoftvertechnológia számos területén igazolták, köztük a szoftvertesztelésben, a programkarbantartásban, a program megértés- és visszafejtésben és a programintegráció területén. A disszertáció megszületését a nagymérető COBOL rendszerek karbantartási feladatainak fontos és aktuális problémája és a különbözı szeletelési alkalmazásokban rejlı lehetıségek motiválták. A programszeletelés területén folytatott kutatás eddig viszonylag kevés figyelmet fordított a COBOL programok szeletelési problémáira, és ahogy ez késıbb kiderült, a feladatra a létezı módszerek nem alkalmazhatók hatékonyan a gyakorlatban. A munka célja 2
egy olyan új statikus programszeletelési megközelítés kidolgozása volt, amely megoldásokat keres azokra a problémákra, amelyek ipari mérető COBOL programok szeletelésekor merülnek fel. A kísérleti eredmények alátámasztják, hogy a kifejlesztett igényvezérelt szeletelési technika alkalmazható nagymérető COBOL programok esetén. Végül fontos kiemelni, hogy a token-terjesztéses technika nem korlátozódik a COBOL programozási nyelvre, így a bemutatott módszer a disszertáció közvetlen célján túlmenıen hozzájárulhat a programszeletelés szélesebb körő gyakorlati alkalmazásához is.
Főbb tudományos eredmények A disszertáció fıbb tudományos eredményeit öt tézisben foglaltam össze.
1. Tézis Megvizsgáltam nagymérető COBOL programok esetén a létezı statikus programszeletelési módszerek alkalmazhatóságát, és arra a következtetésre jutottam, hogy a gyakorlatban a korábbi módszerek nem alkalmazhatóak hatékonyan túlzott futási vagy tárhely igényük miatt. Ipari mérető kódok szeletelése igényvezérelt megközelítést kíván.
A számított programszeletek pontossága rendkívül fontos nagymérető programkódok esetén, hiszen a szükségesnél nagyobb, túl sok felesleges információt tartalmazó programszeletek használhatatlanok a felhasználók számára. A statikus elemzés során a szeletek pontatlanságának több oka lehet. Ilyen a nem megvalósítható programutak problémája, a dinamikus konstrukciók, pointerek használata, amely problémákat nem lehet megoldani az általánosságban. A realizálható utak problémája azonban kezelhetı. Ezek olyan statikusan kiválasztott programutak, amelyek eljárásból való visszatéréskor mindig az utolsó hívási helyhez térnek vissza. Tanulmányok igazolják, hogy a realizálható utak figyelmen kívül hagyása rendkívül megnövelheti az eredmény szelet méretét, ezért a pontatlan megoldások nem alkalmazhatóak nagymérető programkódok esetén. A szeletelésben a hívási kontextus kezelésére két alapvetı megközelítés létezik. Az egyik a hívási verem nyilvántartásán, a másik az ún. rendszer függıségi gráf (SDG) kétmenetes bejárásán alapul [Horwitz et al. 1990]. Az elsı megközelítés azonban az eljárások ismételt feldolgozását igényli különbözı hívási vermek esetén, és exponenciális-robbanáshoz vezet rekurzív programoknál. Az utóbbi megközelítés hatékonyan képes pontos programszeleteket meghatározni az elıre felépített SDG, illetve az ún. összegzı élek segítségével.
3
Azonban a rendszer függıségi gráfok meghatározása rendkívül költséges lehet nagymérető programok esetén. Ennek oka, hogy elızetesen teljes körő adatfolyam-analízist kell végezni minden eljárásban. Továbbá a COBOL-ban használt nagyszámú globális változó miatt minden eljárás belépési- és hívási ponton minden globális változó számára külön paraméter csomópontot
kell
felvenni
a
gráfba,
amelyek
száma
rendkívül
nagy
lehet.
Összehasonlításképpen, az egyik, a kiértékeléshez is használt COBOL program vezérlési folyamgráfja 210 ezer csomópontból állt, míg az SDG 85 millió plusz csomópontot igényelt volna pusztán a paraméter átadások reprezentálására. Továbbá a COBOL-ban az összetett mőveletet megvalósító utasítások esetén, amelyek egy lépésben akár több ezer változónak is értéket adhatnak, a különbözı definíciók számára külön csomópontot kell felvenni (a használt gráf bejárási algoritmus miatt). Végül az összes összegzı él meghatározása szintén rendkívül idıigényes lehet, amely több órát (vagy akár napot) is igénybe vehet. Összefoglalva, az SDG-alapú módszer használata, pontossága ellenére rendkívül idı- és tárhely igényes lehet ipari mérető COBOL programok esetén, amelyek inkább egy igényvezérelt megközelítést kívánnának. Ezek az eredmények a disszertáció elsı fejezetében találhatóak. A szerzı kapcsolódó publikációi: [1, 3, 5, 6].
2. Tézis Kifejlesztettem egy új igényvezérelt statikus programszeletelési technikát, amely a vezérlési folyamgráfokon történı token terjesztés révén pontos programszeleteket képes meghatározni, realizálható utak figyelembevételével. Bizonyítottam a módszer helyességét és teljességét.
A módszer alapötlete az, hogy a definíció-felhasználás láncokat (adatfolyam-szeletelés esetén) a vezérlési folyamgráfon történı token terjesztéssel derítjük fel. A token terjesztés során a függıségi láncok csomópontjait megjelöljük, és a token terjesztés végeztével az eredmény szeletet a megjelölt csomópontok alkotják. A token egyfajta elérı definíció információ (elıremenı szeletelés esetén), amely egy adott változó egy adott definíciójához, ill. ugyanennek a változónak különbözı definícióihoz köthetı. A token terjesztés a szeletelési kritérium csomópontjából indul, a szeletelési kritérium definíciójának megfelelıen létrehozott token-nel, amely token-t definíciómentes utakon terjesztjük. Amennyiben ez a token egy olyan csomópontba terjed be, amely csomópont a token változójára felhasználást tartalmaz, akkor ezt a csomópontot szeletbelinek jelöljük meg (definíció-felhasználás pár). Továbbá, minden olyan definiált változóból, amelyekre a felhasználás hatással van, újabb 4
token terjesztést indítunk az új definícióknak megfelelı token-ekkel, a közvetett függıségek felderítésére (definíció-felhasználás láncok). Hívási
kontextus
információ
nélkül
azonban
a
token-ek
minden
lehetséges
(definíciómentes) programutat bejárnának, köztük a nem realizálhatóakat is. Ezért a token-ek ún. visszalépési információt tartalmaznak, amely hívásból való visszatéréskor a token-eket olyan visszatérési helyekre irányítja, amelyek így realizálható útbejárásoknak felelnek meg. A fent leírt, token terjesztésen alapuló adatfolyam szeletelési módszer kiterjeszthetı a vezérlési függıségek követésére is, azaz teljes programszeletek meghatározására, ún. vezérlési token-ek terjesztésével. A bemutatott algoritmus a vezérlési folyamgráfokon alapul, amely könnyebben adaptálható a különbözı programozási nyelvekben használt konstrukciók reprezentálására, egyúttal megtartja az SDG-alapú módszerek által elérhetı szeletpontosságot, azáltal, hogy az összegzı éleket igényvezérelt módon számítja. Ezek az eredmények a disszertáció második fejezetében találhatóak. A szerzı kapcsolódó publikációi: [1, 3].
3. Tézis A bemutatott igényvezérelt módszer egy prototípusát implementáltam, és ennek teljesítményét ipari mérető COBOL kódokon értékeltem ki. Az eredmények alátámasztják a módszer hatékonyságát azokban az esetekben, amikor a szeletméret ésszerő határokon belül marad. Hosszú számítási idık esetén a felhasználók számára értelmezhetetlen, túlságosan nagymérető programszeleteket kapunk.
A bemutatott módszer kiértékeléséhez az algoritmus egy prototípusát implementáltam. A szeletelési kísérleteket egy nagymérető, több mint egy millió soros COBOL rendszeren végeztem, húszezer, véletlenszerően kiválasztott szeletelési kritériumon. Mind az adatfolyam, mind pedig teljes szeletelési idıket és szeletméreteket mértem, elıre- és hátramenı esetben. Az eredmények azt mutatják, hogy a módszer rövid idı alatt képes pontos programszeletek meghatározására, hosszabb számítási idık esetén az eredményszeletek mérete olyan nagy, hogy a szeletek amúgy sem értelmezhetık a felhasználók számára. Ezek az eredmények a disszertáció harmadik fejezetében találhatóak. A szerzı kapcsolódó publikációja: [1].
5
4. Tézis Kifejlesztettem egy programszelet megértést támogató technikát. Az algoritmus alkalmas konkrét függıségi láncok meghatározására az indokolandó szeletelemekhez, amelynek hatékonyságát tapasztalati eredmények támasztják alá.
Nagymérető programszeletek, de akár a csak néhány tíz elemet tartalmazó programszeletek megértése is gyakran nagyon nehéz feladat. A bemutatott algoritmus erre a problémára ad megoldást azáltal, hogy a számított programszelet tetszılegesen kiválasztott eleméhez automatikusan egy konkrét függıségi láncot határoz meg, amely függıségi láncot vezérlési információkkal lát el a könnyebb követhetıség kedvéért. A szeletek ellenırzése és megértése a javasolt eszköz nélkül rendkívül idıigényes és nagy szakértelmet kívánó feladat lenne. Ezek az eredmények a disszertáció negyedik fejezetében találhatóak. A szerzı kapcsolódó publikációja: [2].
5. Tézis
A token terjesztés alapú programszeletelési algoritmus több továbbfejlesztési
lehetıségét mutattam be. Megmutattam, hogy ezek a javítási lehetıségek a módszer idı vagy tárhely igényét képesek csökkenteni. Módosított algoritmusokat mutattam be, amelyek alkalmasak definíció-felhasználás gráfok, programvágások, darabolások meghatározására.
Nagymérető programkódok esetén a terjesztendı- és tárolandó token-ek száma igen nagy lehet. Ezért különbözı javítási lehetıségeket, algoritmustervezési alternatívákat javasoltam, amelyek révén csökkenthetı a módszer futási idı- vagy tárhely igénye. A tárolandó token-ek száma csökkenthetı, ha elıször meghatározzuk az eljárások topologikus sorrendjét a hívási gráf alapján, és az eljárásokat fordított hívási sorrendben dolgozzuk fel. A terjesztendı token-ek száma csökkenthetı a folyamélek igényvezérelt meghatározásával, továbbá, ha elıre kiszámítjuk az eljárások ún. GREF-GMOD-KILL halmazait, amelyek révén ki tudjuk szőrni a felesleges token terjesztéseket. Az újabb és újabb szeletelési feladatok futási idejét csökkenthetjük, ha a szeletelések során kapott összegzı él információkat elmentjük és felhasználjuk a következı szeletelés során. Egy módosított algoritmust mutatok be, amely alkalmas definíció-felhasználás gráfok meghatározására. Ezek a gráfok a program megértésben és az adatfolyam-alapú tesztelésben nyújtanak segítséget. Azt is megmutatom, hogy hogyan alkalmazható a token-terjesztéses módszer program vágások és darabolások meghatározására. Ezek az eredmények a disszertáció ötödik fejezetében találhatóak. A szerzı kapcsolódó publikációja: [3]. 6
Tudományos publikációk Publikációk a disszertáció témájában Folyóiratcikkek [1]
Ákos Hajnal, István Forgács. 2012. A demand-driven approach to slicing legacy COBOL systems. JOURNAL OF SOFTWARE: EVOLUTION AND PROCESS, 24(1), pp. 67–82. Impakt faktor: 0.844, független idézı: 1
[2]
Ákos Hajnal, István Forgács. 2012. Understanding program slices. ACTA CYBERNERTICA (megjelenés alatt).
Konferenciacikkek [3]
Ákos Hajnal, István Forgács. 2002. A precise demand-driven def-use chaining algorithm. In: 6th European Conference on Software Maintenance and Reengineering (CSMR’2002), IEEE Computer Society, pp. 77–86. Független idézı: 2
[4]
Ákos Hajnal, István Forgács. 1998. An applicable test data generation algorithm for domain errors. In: 1998 ACM/SIGSOFT International Symposium on Software Testing and Analysis (ISSTA '98), ACM New York, pp. 63–72. SOFTWARE ENGINEERING NOTES, 23(2), ACM New York, pp. 63–72. Független idézı: 12
[5]
István Forgács, Ákos Hajnal. 1998. Automated test data generation to solve the Y2k problem. In: 2nd International Software Quality Week Europe 1998 (QWE'98), p. 10 (paper 2S).
[6]
István Forgács, Ákos Hajnal, Éva Takács. 1998. Regression slicing and its use in regression testing. In: 22nd Annual International Computer Software and Applications Conference (COMPSAC'98), IEEE Computer Society, pp. 464–469. Független idézı: 1
7
Egyéb publikációk [7]
István Forgács, Ákos Hajnal. 2011. Forráskód-analízis: Olvassunk a sorok között! COMPUTERWORLD SZÁMÍTÁSTECHNIKA, XLII:(41), pp. 10–12.
[8]
István Forgács, Ákos Hajnal. 1997. Szoftver tesztelés. Jegyzet Szoftver minıség és tesztelés tárgyhoz, BME, ELTE Doktori Iskola, 1997/1998-as tanév, p. 41.
További publikációk Folyóiratcikkek [9]
David Isern, Antonio Moreno, David Sánchez, Ákos Hajnal, Gianfranco Pedone, László Zsolt Varga. 2011. Agent-based execution of personalised home care treatments. APPLIED INTELLIGENCE, 34(2), pp. 155–180. Impakt faktor: 0.849, független idézı: 2
Könyvfejezetek [10]
Ákos Hajnal, Tamás Kifor, Gergely Lukácsy, László Zsolt Varga. 2009. Web services as XML data sources in enterprise information integration. In: Services and Business Computing Solutions with XML: Applications for Quality Management and Best Processes (P. Hung, Ed.), IGI Global, pp. 82–97. Enterprise Information Systems: Concepts, Methodologies, Tools and Applications, 2011, Hershey PA: Information Science Reference, pp. 972–985.
[11]
Ákos Hajnal, Antonio Moreno, Gianfranco Pedone, David Riano, László Zsolt Varga. 2008. Formalizing and leveraging domain knowledge in the K4CARE home care platform. In: Semantic knowledge management: An ontology-based framework (A. Zilli, E Damiani, P. Ceravolo, A. Corallo, G. Elia, Eds.), Information Science Reference, pp. 279–302.
[12]
László Zsolt Varga, Ákos Hajnal, Zsolt Werner. 2005. The WSDL2Agent tool. In: Software Agent-Based Applications, Platforms and Development Kits (R. Unland, M. Klusch, M. Calisti, Eds.), Whitestein Series in Software Agent Technologies, Birkhauser Basel, pp. 197–223.
8
Konferenciacikkek [13]
Tamás Kifor, Tibor Gottdank, Ákos Hajnal, Péter Baranyi, Brúnó Korondi, Péter Korondi. 2011. Smartphone emotions based on human-dog interaction. In: 2nd International Conference on Cognitive Infocommunications: CogInfoCom 2011, IEEE Computer Society, pp. 1–6.
[14]
Tamás Kifor, Tibor Gottdank, Ákos Hajnal, Csanád Szabó, András Róka, Brúnó Korondi, Péter Korondi. 2011. EthoPhone, human-dog interaction inspired affective computing for smartphone. In: Proceedings IEEE/ASME International Conference on Advanced Intelligent Mechatronics, IEEE Computer Society, pp. 542–547.
[15]
Ákos Hajnal, David Isern, Antonio Moreno, Gianfranco Pedone, László Zsolt Varga. 2007. The role of knowledge in designing an agent platform for home care. In: 2nd International Conference on Knowledge Management in Organizations (KMO), pp. 16–26. Független idézı: 2
[16]
Ákos Hajnal, David Isern, Antonio Moreno, Gianfranco Pedone, László Zsolt Varga 2007. Knowledge driven architecture for home care. In: Multi-agent systems and applications V: 5th International Central and Eastern European Conference on Multiagent Systems (CEEMAS 2007), pp. 173–182. LECTURE NOTES IN ARTIFICIAL INTELLIGENCE, Vol. 4696, Springer-Verlag, pp. 173–182. Független idézı: 11
[17]
Ákos Hajnal, Gianfranco Pedone, László Zsolt Varga. 2007. Ontology-driven agent code generation for home care in Protégé. In: 10th International Protégé Conference: Budapest, Hungary, pp. 91–93. Független idézı: 4
[18]
Ákos Hajnal, Tamás Kifor, Gianfranco Pedone, László Zsolt Varga. 2007. Benefits of provenance in home care. In: Healthgrid 2007. STUDIES IN HEALTH TECHNOLOGY AND INFORMATICS, Vol. 126: From genes to personalized healthcare: grid solutions for the life sciences (N. Jacq, Y. Legré, H. Muller, I. Blanquer, V. Breton, D. Hausser, V. Hernández, T. Solomonides, M. Hofman-Apitius, Eds.), IOS Press, pp. 330–337. Független idézı: 1
9
[19]
László Zsolt Varga, Ákos Hajnal, Zsolt Werner. 2004. An agent based approach for migrating web services to semantic web services. In: 11th International Conference on Artificial Intelligence: Methodology, Systems (AIMSA 2004). LECTURE NOTES IN COMPUTER SCIENCE, Vol. 3192, Springer-Verlag, pp. 371–380. Független idézı: 12
[20]
László Zsolt Varga, Ákos Hajnal. 2003. Engineering web service invocations from agent systems. In: 3rd International/Central and Eastern European Conference on Multi-Agent Systems (CEEMAS 2003). LECTURE NOTES IN COMPUTER SCIENCE, Vol. 2691, Springer-Verlag, pp. 626–636. Független idézı: 15
Egyéb publikációk [21]
Jonathan Dale, Ákos Hajnal, Martin Kernland, László Zsolt Varga. 2003. Integrating web services into Agentcities. Agentcities Technical Recommendation Document (actf-rec-00006). Független idézı: 10
Összefoglalás publikációk
impakt faktor
független idéző
folyóiratcikk
3
1.693
3
könyvfejezet
3
–
0
konferenciacikk
12
–
60
egyéb
3
–
10
összesen
21
1.693
73
Hivatkozások BINKLEY, D. 2007. Source code analysis: A road map. In FOSE '07: 2007 Future of Software Engineering, 104–119. HORWITZ, S., REPS, T.,
AND
BINKLEY, D. 1990. Interprocedural slicing using dependence
graphs. In ACM Transactions on Programming Languages and Systems, 12(1), 26–60. WEISER, M. 1984. Program slicing. In IEEE Transactions on Software Engineering, 10(4), 352–357.
10
