Mogelijke parser oplossingen



Dovnload 32.47 Kb.
Datum20.08.2016
Grootte32.47 Kb.

Framework


Om mogelijke beveilingsfouten in broncode van software op te sporen is er gekozen om een framework te maken. Het framework bestaat uit een parser die de broncode inleest en interpreteert en een datastructuur waarin deze wordt opgeslagen. De plaats van het framework is uitgewerkt in figuur [nummer].

Als eerste worden de verschillende parser oplossingen beschreven gevolgd door een vergelijking en keuze van een van de parser in [paragraaf nummer]. Vervolgens wordt de datastructuur beschreven in [paragraaf nummer]. De samenwerking tussen de parser en de datastructuur wordt beschreven in [paragraafnummer]. Als laatste wordt de test van het framework beschreven. Het Complete klassendiagram is terug te vinden in de bijlage[letter]


Mogelijke parser oplossingen


Bij een goede analyse van de broncode wordt zowel gekeken naar de woorden als naar de grammatica van de broncode. Simpel alleen zoeken op functienamen die potentieel onveilig zijn biedt geen goede oplossing. Het is namelijk zo dat bepaalde functies alleen onveilig zijn bij bepaalde parameters. Het framework dient dus meer intelligentie te hebben dan alleen het herkennen van woorden. Een andere reden is dat indien een functienaam bijvoorbeeld in een string staat of als commentaar is het ook niet gevaarlijk aangezien de functie dan niet wordt uitgevoerd. Daarom is het nodig te werken met een parser.

Zelf parser maken


Een mogelijk oplossing is het zelf maken van een parser. Dit lijkt een simpele opdracht. In de realiteit is dit niet zo simpel. Een programmeertaal bezit een van te voren bepaalde syntax dus het is in theorie prima mogelijk om aan de hand van de syntax een soort parser te maken. Het complexe ligt in het probleem dat er veel regels zijn en in een taal er een groot aantal complexe constructies kunnen voorkomen. Hierbij valt te denken aan commentaar van de programmeur. Dit dient namelijk genegeerd te worden. Het commentaar begint met de volgende syntax: /*. Maar deze combinatie kan ook voorkomen in een string en dan dient deze weer genegeerd te worden. Dit is een klein simpel voorbeeld zo zijn er vele meer te bedenken.

Een ander probleem is dan er alleen wordt gekeken naar de correctheid van woorden maar niet of de code voor de rest correct is. Het is dus dan mogelijk om code in te voeren die niet eens door de compiler komt. Verder blijft het mogelijk dat de zelfgemaakte parser niet volledig werkt aanwezig.


Lex / Yacc


Zowel Lex als Yacc zijn programma generatoren. Zoals de naam het zegt maken ze dus een programma aan de hand van bepaalde input. Lex en Yacc zijn twee gescheiden applicaties die vaak samen worden gebruikt. Dit komt omdat ze op een bepaalde manier afhankelijk zijn van elkaar.

Lex is een lexer. Een lexer zet een zin om in losse woorden aan de hand van te voren bepaalde regels. Deze regels zijn een soort woordenboek, want woorden in een taal voldoen aan bepaalde regels. Zo is het in het Nederlands niet mogelijk dat een woord eindigt op een v. Een lexer analyseert een input bestaande uit zinnen en zet deze om in losse woorden indien de woorden voldoen aan de regels. Als we dit toepassen op een Nederlandse zin is dat vrij eenvoudig. Een lexer scheidt dan op de spatie. Dus de zin wordt geretourneerd als allemaal losse woorden, ook wel tokens genoemd. Bij programmeertalen is dat een stuk ingewikkelder. Het is daar niet voldoende om alleen op spatie te scheiden. Lex heeft als ouput een stream aan tokens, deze worden opgevangen door Yacc.




Maar alleen correcte woorden zeggen vrij weinig. Woorden die samen in een zin zitten hebben een betekenis. Even een simpel voorbeeldje. Stel we hebben een Nederlandse zin dat kunnen we die ontleden naar onderwerp, werkwoord, zelfstandig naamwoord, lijdendvoorwerp enz. YACC doet hetzelfde met programmeercode aan de hand van grammaticale regels van een programmeertaal. Semantiek geeft de betekenis weer van de een grammaticale constructie weer. Neem bijvoorbeeld: "Het groene gras". Lijkt een correcte zin maar is het niet, het is een Pleonamse (gras is groen dus dubbelop). Met kennis over de semantiek kunnen fouten uit taal worden gehaald. Terugkoppeld naar informatica, indien je een programma compileert dan kijkt de compiler of je voldoet aan de grammaticale regels van de taal, zoniet dan wordt het programma niet gecompileerd en volgt een foutmelding. Yacc doet in principe hetzelfde, het probeert het controleert de woorden die binnenkomen uit de lexer op de grammaticale regels van taal en indien hier niet aan voldaan wordt dan geeft hij een foutmelding.


Yaxx


Yaxx is een uitbreiding op de Lex / Yacc combinatie. Er is een skeleton toegevoegd aan Yacc. Dit heeft als gevolg dat er output wordt wegschreven naar een bestand tijdens het parsen van een bronbestand. In deze output die in het XML formaat is staat de volledige parsettree. Een parsetree in een boom aan gegevens met alle regels die van toepassing zijn om een woord in broncode bestand. In tegenstelling met de standaard Lex / Yacc combinatie ontstaat er dus ook output indien het programma correct is en biedt de output inzicht in de grammaticale structuur van het programma zodat deze geanalyseerd kan worden.





Overige bestaande parsers


Naast de hier boven beschreven parser zijn ook andere bekeken. Deze stellen dat ze de zelfde functionaliteiten hebben als lex / yacc. Het is een combinatie van die twee programma's in een. De volgende parsers zijn bekeken: SabbleCC en ANLTR. Bij deze parsers is in allebei de gevallen een grammatica voor C aanwezig. Een contrast met Lex/Yacc is dat deze parsers in JAVA zijn.

Gekozen parser oplossing


Bij het kiezen van de parser is er gelet op de volgende eigenschappen. Ten eerste dienen er werkende grammatica en lexicale regels aanwezig te zijn voor de programmeertaal C. Ten tweede dient er een output te zijn waarop een analyse kan worden uitgevoerd. Als laatste is er gekeken naar de programmeertaal waarin de parser is. Aangezien de programmeertaal C++ het meest is behandeld tijdens de opleiding heeft deze de voorkeur. In de onderstaande tabel staan de besproken mogelijke parsers opgenomen en de net genoemde critera.




Zelfgemaakte

Parser


Lex / Yacc

Lex / Yaxx

ANTLR

SableCC

C Grammatica

Zelf maken

Aanwezig

Aanwezig

Aanwezig maar niet werkend

Aanwezig niet werkend

Handzame output

Zelf maken

Zelf maken dmv Skeleton

Aanwezig

Nee

Onbekend

Programmeer

taal


Vrije keuze

C / C++

C / C++ en XML

Java

Java

Uit tabel (nummer) blijkt duidelijk de Lex / Yaxx combinatie de beste oplossing biedt aan de hand van de gestelde criteria. Er hoeft namelijk het minst aan gewijzigd, verbeterd of uitgebreid worden om er mee te kunnen werken in het framework. Verder kan er gewerkt worden in C++ en XML.

Datastructuur


Om de code te kunnen controleren op mogelijke beveilingsfouten wordt de code door de parser is gehaald opgeslagen in een datastructuur. Aan de hand van deze datastructuur wordt dan de analyse gemaakt.

Boomstructuur


Bij het parsen door Yaxx wordt een parsetree gemaakt in een bestand in het XML formaat. Een parsetree is zoals de naam al doet vermoeden een boomstructuur met daarin alle tokens uit het sourcebestand geplaatst. Tevens is uit de boom op te maken wat voor het token het betreft, en wat de relatie is tot andere tokens. In figuur [nummer] staat een eenvoudig parsetree voor de expressie (N=2) AND (S > 80.000).


De parsetree van een stuk sourcecode is vele male groter en bevat ook veel informatie die niet relevant is voor het zoeken op fouten. Toch is het de hiërarchische structuur van de parsetree een prima structuur om mee verder te gaan. Kijkend naar het stuk code[nummer]. De code is niet correct maar biedt prima de mogelijkheid het nut van een boomstructuur weer te geven. Variabelen in de programmeertaal leven van accolade tot accolade. De integer a die wordt geïnitialiseerd op regel drie leeft tot de sluit accolade van regel tien. De instructie op regel zes kan worden uitgevoerd aangezien de variabele a nog steeds bekend is. De integer b die wordt aangemaakt op regel vijf leeft maar tot regel acht. Hierdoor wordt meteen duidelijk dat de opdracht in regel negen niet kan worden uitgevoerd aangezien de variabele b niet meer bestaat. Als in de instructie in regel negen in plaats van de variabele b a werd gebruikt is er niks aan de hand.




1. int main()

2 {

3 int a = 0;

4 {

5 int b = 5;

6 printf(“a = %d”, a);

7 printf(“b = %d”, b);

8 }

9 printf(“b = %d”, b);

10 }

Aangezien C++ in de STL klasse geen boom kent diende er een alternatief gezocht te worden. Een mogelijkheid is om zelf een boomstructuur te implementeren maar naar kort zoekwerk is er een library gevonden[verwijzing naar website] die voldeed aan de eisen van een boomstructuur die nodig is. Een voordeel is dat deze al volledig geïmplementeerd is, er voorbeeld code beschikbaar is en de mogelijkheid tot het gebruik van iteratoren wat het uiteindelijke werken met de boom een stuk eenvoudiger maakt.


Bladeren in de boomstructuur


Zoals al vermeld in de vorige paragraaf bezit de door Yaxx gegenereerde parsetree teveel informatie. Er is besloten de volgende informatie op te slaan. Voor elke accolade die in de sourcecode staat wordt een nieuw compound geopend. Deze compounds dienen als de bladeren in de boom van de datastructuur. Een compound bestaat uit een aantal instructies. Bij deze instructies is er onderscheid gemaakt tussen de volgende drie instructies.

Ten eerste hebben we een verschil tussen declaraties van variabelen. Hier worden variabelen geïnitialiseerd. Het is van belang om te weten of een variabelen van een bepaald compound is of dat het een parameter is of een resultaat van een onveilige inleesfunctie.

Ten tweede hebben we statements. Statements zijn instructies zoals optellingen of functie aanroepen. Statements zijn van belang aangezien deze potentieel onveilig kunnen zijn. Later bij het scannen naar onveilige functies dienen de statements doorlopen te worden. Statements kunnen een lijst bevatten met parameters die worden mee gegeven aan de statement. Dit is van belang aangezien bij bepaalde functies bepaalde parameters er voor kunnen zorgen dat een functie onveilig is.

Als laatste hebben we parameters die gelden in een compound. Indien een compound een functiedefinitie is gelden de parameters van de functie in compound als variabelen.

Door deze structuur wordt het mogelijk de statements te controleren op onveilige functies, dit kan simpel weg door het opvragen van de functienaam maar ook door het analyseren van de parameters van de functie. Door de boomstructuur is het mogelijk te zoeken waar de parameters worden gedeclareerd en in welke statements ze eventueel worden gewijzigd. Dit kan gedaan worden door het doorlopen van de declaraties en ingeval van functieparameters omhoog te gaan in de boom aangezien deze gedeclareerd en eventueel door een statement gewijzigd zijn in hoger blad.


Van XML naar de Datastructuur


Het programma heeft globaal nu de structuur weergegeven in figuur [nummer]. De Parser is bekend, de datastructuur. Maar nog niet hoe de XML output van de parser wordt omgezet naar de Datastructuur.

Er zijn verschillende library's voor C++ om XML in te lezen en te schrijven. Voor dit probleem is alleen het inlezen van belang. Er is gekozen om gebruiken te maken van LibXML [verwijzing] op aanrade van de heer de Goede. Hier is voor gekozen vanwege meerdere redenen. Ten eerste is het een veel gebruikte opensource library. Verder zijn er vele voorbeelden van aanwezig en een duidelijk API waardoor het eenvoudig op te pakken is. Een ander voordeel voor LibXML API overeenkomt met de API van Microsoft .Net die al bekend was bij de programmeurs. Als laatste voldeed de API van LibXML aan alle eisen om het XML bestand in te lezen.


Samenhang


Het parser gedeelte wordt gegenereerd door Lex en Yaxx, zoals al eerder vermeld zijn dit programma generators. Deze output is in de programmeertaal C. De output van de parser is een XML bestand. Dit dient te worden ingelezen door de XMLreader die daarmee de datastructuur opbouwd. Het programma bestaat in feite uit twee losse programma’s. Ten eerste de parser, de output van de van de programma generatoren Lex en Yaxx gecompileerd tot de parser. En de datastrucuut die de ouput van de parser inleest, dit is geschreven in C++. Voor de gebruiker is het niet zichtbaar dat het twee programma’s bestaat. Het is wenselijk dit in de toekomst samen te voegen tot een programma, vanwege de beperkte tijd van dit project is daar geen prioriteit aangeven.

Test


Het framework is uitvoerig getest met stukken ansi C code als invoer. Hier is heel eenvoudig mee begonnen met een simpel Hello World programma en uiteindelijk geëindigd met een volledige editor (JOE editor). Hier kwamen een aantal problemen boven drijven die interessant zijn om te beschrijven. Als eerste bleek uit de tests dat er geen regelnummers door kwamen vanuit de parser. Verder bleken er problemen te zijn met grote stukken commentaar. Ook waren er problemen met precompiler instructies. Als laatste wordt beschreven dat er problemen zich voordeden met gedefineerde datatypes.

Regelnummers


Voor een volledige output zijn regelnummers van belang. Deze bieden de gebruiker inzicht in waar de fout zich voor doet. Jammer genoeg werd dit niet door de parser ondersteund. Daarom is besloten de parser aan te passen. Lex heeft de mogelijkheid C code uit te voeren. Met deze mogelijkheid is er een functie toegevoegd die een teller impliceert. Om de functie aan te kunnen roepen zijn de regels van de Lexer aangepast zodat deze bij een nieuwe regel altijd de tel functie aanroept. Nu is er dus de mogelijkheid om op te vragen aan de lexer op welke regel je zit. Dit opvragen dient te gebeuren door Yaxx. Daarom is deze zo aangepast dat deze het regelnummer opvraagt en mee wegschrijft in het XML bestand.

Commentaar


Uit tetst bleek dat de parser vast liep bij grote stukken commentaar. Dit lag aan lexer. Zoals al vermeld heeft de lexer de mogelijkheid om stukken C code uittevoeren, indien de lexer commentaar zag beginnen begon hij deze op te slaan in een buffer door middel van een functie waarna er niks meer mee gebeurde. Bij grote stukken commentaar paste dit niet meer in de buffer. Het is voor de werking van dit programma helemaal niet relevant om commentaar op te slaan. Daarom is besloten het commentaar niet op te slaan. De functie in de lexer die het commentaar afhandelde is zo aangepast dat deze het commentaar niet meer opslaat. Verder wordt er ook de regelnummer teller aangeroepen zodat de regelnummers wel synschroon blijven lopen.

Precompiler instructies


Precompiler instructies kwamen niet voor in de grammatica van Yaxx. Dit is vrij logisch aangezien precompiler instructies niet behoren tot de programmeetaal. Om dit op te lossen is er besloten de lexer aan te passen zodat deze instructies beginnende met een # weggooit en niet doorgeeft aan Yaxx.

Gedefinieerde datatypes


Als laatste deed zich het probleem voor met gedefinieerde datatypes zoals bijvoorbeeld structs. Dit wordt wel ondersteund door de grammatica van Yaxx het probleem zit erin dat hij deze niet onthoudt. Het probleem doet zich in de volgende situatie voor. Er wordt een stuct gedefinieerd en deze wordt daarna gebruikt als return waarde van een functie die wordt gedefinieerd. Yaxx komt in dat geval een onbekend datatype tegen omdat hij de struct definitie niet onthouden heeft en dat is in tegenstrijd met de grammatica. Er zijn pogingen ondernomen om de grammatica aan te passen dit leidde tot “shift reduce conflicts”. Neem bijvoorbeeld de volgende code:

if (A) if (B) statement1; else statement2;


Hoort statement2 als else conditie bij de eerste of tweede if? De enige oplossing is zoals al vermeld Yaxx laten bijhouden welke type definities er al zijn gedaan, en tegelijk ook te controleren of type definities nog mogelijk zijn omdat de naam eventueel al in gebruik is.

Conclusie


Uit het testen blijkt dat de gekozen oplossing van de parser is goede keuze is geweest. Dit vanwege het feit dat deze op de gedefinieerde datatypes na geen problemen heeft met het parsen van ANSIC code. Verder biedt de output van de parser de mogelijkheid tot maken van instinctieve datatstructuur in de vorm van een boom.



De database wordt beschermd door het auteursrecht ©opleid.info 2017
stuur bericht

    Hoofdpagina