AST (Abstract Syntax Tree)

AST (Abstract Syntax Tree) är en grafisk representation av källkod som i första hand används av kompilatorer för att läsa kod och generera binärfiler.

Till exempel kommer AST:

while b ≠ 0
if a > b
a := a − b
else
b := b − a
return a

att se ut så här:

Transformationen från källkod till ett AST är ett mycket vanligt mönster när man bearbetar någon typ av strukturerad data. Det typiska arbetsflödet bygger på att ”skapa en parser som omvandlar rådata till ett grafbaserat format som sedan kan konsumeras av en renderingsmotor”.

Detta är i princip processen att omvandla rådata till i starkt typade minnesobjekt som kan manipuleras programmatiskt.

Här är ett annat exempel från det riktigt coola online-verktyget astexplorer.net:

Bemärk hur i bilden ovan den råa texten på DOT-språket har konverterats till ett objektträd (som också kan konsumeras/sparas som en json-fil).

Som utvecklare om du kan ”se kod eller rådata som ett diagram” har du gjort ett fantastiskt paradigmskifte som kommer att hjälpa dig enormt över din vårdgivare.

Till exempel har jag använt ASTs och anpassade parsers för att:

  • skriva tester som kontrollerar vad som faktiskt händer i koden (enkelt när man har tillgång till en objektmodell av koden)
  • konsumera loggdata som normala ”regex”-baserade parsers hade svårt att förstå
  • genomföra statisk analys av kod som är skriven i anpassade språk
  • omvandla datadumps till in-minnesobjekt (som sedan enkelt kan transformeras och filtreras)
  • skapa transformerade filer med delar av flera källkodsfiler (som jag kallade MethodStreams och CodeStreams) – se exempel nedan för hur detta ser ut i praktiken
  • genomföra anpassad kodrefaktorisering (t.ex. för att automatiskt åtgärda säkerhetsproblem i koden) – se exempel nedan för hur detta ser ut i praktiken

När man bygger en analysator för en viss datakälla, är en viktig milstolpe att kunna gå från AST tillbaka till originaltexten (utan dataförlust).

Det är exakt så här som refaktorisering av kod i IDE fungerar (t.ex. när du byter namn på en variabel och alla instanser av den variabeln byter namn).

Här är hur denna rundgång fungerar:

  1. starta med fil A (dvs. källkoden)
  2. skapa AST för fil A
  3. skapa fil B som en omvandling från AST
  4. fil A är lika med fil B (byte byte)

När detta är möjligt blir det lätt att ändra koden programmatiskt, eftersom vi kommer att manipulera starkt typade objekt utan att behöva oroa oss för skapandet av syntaktiskt korrekt källkod (som nu är en omvandling från AST).

Skriva tester med hjälp av ASTs objekt

När du börjar se din källkod (eller data som du konsumerar) som ”bara en AST-parser bort från att vara objekt som du kan manipulera”, kommer ett helt ord av möjligheter och förmågor att öppna sig för dig.

Ett bra exempel är hur man upptäcker ett visst mönster i källkoden som man vill försäkra sig om att det förekommer i ett stort antal filer, låt oss säga till exempel att man vill: ”se till att en viss auktoriseringsmetod (eller datavalidering) anropas på varje exponerad webbtjänstmetod”?

Detta är inte ett trivialt problem, eftersom om du inte kan programmera ett test som kontrollerar detta anrop är dina enda alternativ:

  1. skriv ett ”standarddokument/wiki-sida” som definierar detta krav och se till att alla utvecklare läser det, förstår det och, ännu viktigare, följer det
  2. kontrollera manuellt om standarden/kravet har implementerats på rätt sätt (vid kodgranskningar i Pull Requests)
  3. försök att använda automatisering med ”regex”-baserade verktyg (kommersiellt eller open source), och inser att det är mycket svårt att få bra resultat med det
  4. återfall på manuella QA-tester (och säkerhetsgranskningar) för att upptäcka eventuella blinda fläckar

Men när du har möjlighet att skriva tester som kontrollerar detta krav, så är det här vad som händer:

  1. skriva tester som konsumerar kodens AST för att mycket explicit kunna kontrollera om standarden/kravet har implementerats/kodats korrekt
  2. via kommentarer i testfilen kan dokumentationen genereras från testkoden (i.dvs. inget extra steg krävs för att skapa dokumentation för denna standard/det här kravet)
  3. kör dessa tester som en del av det lokala bygget och som en del av den huvudsakliga CI-pipelinen
  4. genom att ha ett misslyckat test kommer utvecklarna att få veta så fort som möjligt när ett problem har upptäckts, och kan åtgärda det mycket snabbt

Det här är ett perfekt exempel på hur man skalar arkitektur- och säkerhetskrav, på ett sätt som är inbäddat i mjukvaruutvecklingslivscykeln.

Vi behöver ASTs för äldre och molnmiljöer

Desto mer man sätter sig in i ASTs, desto mer inser man att de är abstraktionslager mellan olika lager eller dimensioner. Ännu viktigare är att de gör det möjligt att manipulera ett visst skikts data på ett programmatiskt sätt.

Men när man tittar på de nuvarande legacy- och molnmiljöerna (den del som vi kallar ”Infrastructure as code”) kommer man att se att stora delar av dessa ekosystem i dag inte har AST-parsers för att omvandla sin verklighet till programmerbara objekt.

Det här är ett utmärkt forskningsområde där man skulle kunna fokusera på att skapa DSL:er (domänspecifika språk) antingen för äldre system eller för molntillämpningar (välj en av dem eftersom båda kommer att ha helt olika uppsättningar av källmaterial). Ett exempel på den typ av DSL som vi behöver är ett språk för att beskriva och kodifiera beteendet hos Lambda-funktioner (nämligen vilka resurser de behöver för att exekvera och vad som är det förväntade beteendet hos Lambda-funktionen)

MethodStreams

Ett av de kraftfullaste exemplen på AST-manipulation som jag har sett är MethodStreams-funktionen som jag lade till O2-plattformen.

Med den här funktionen kunde jag programmeringsmässigt skapa en fil som baseras på anropsträdet för en viss metod. Denna fil innehöll all källkod som var relevant för den ursprungliga metoden (genererad från flera filer) och gjorde en enorm skillnad när jag gjorde kodgranskningar.

För att förstå varför jag gjorde detta börjar vi med det problem jag hade.

Redan 2010 gjorde jag en kodgranskning av en .Net-applikation som hade en miljon rader kod. Men jag tittade bara på WebServices-metoderna, som bara täckte en liten del av den kodbasen (vilket var logiskt eftersom det var dessa metoder som exponerades för internet). Jag visste hur jag skulle hitta de internetexponerade metoderna, men för att förstå hur de fungerade var jag tvungen att titta på hundratals filer, dvs. de filer som innehöll kod i dessa metoders exekveringssökväg.

Med tanke på att jag i O2-plattformen redan hade en mycket stark C#-parser och stöd för refaktorisering av kod (implementerat för REPL-funktionen) kunde jag snabbt skriva en ny modul som:

  1. med utgångspunkt i webbtjänstmetod X
  2. beräknade alla metoder som anropas från den metoden X
  3. beräknade alla metoder som anropas av 2. (rekursivt)
  4. fånga AST-objekten från alla metoder som identifierats i de föregående stegen
  5. skapar en ny fil med alla objekt från 4.

Denna nya fil var fantastisk, eftersom den ENDAST innehöll den kod som jag behöver läsa under min säkerhetsgranskning.

Men det blev ännu bättre, eftersom jag i den här situationen kunde lägga till validerings-RegExs (som tillämpas på alla WebServices-metoder) högst upp i filen och lägga till källkoden för de relevanta Stored Procedures längst ner i filen.

En del av de genererade filerna hade över 3 000 rader kod, vilket var en enorm förenkling av de över 20 filer som innehöll dem (som förmodligen hade över 50 000 rader kod).

Här är ett bra exempel på att jag kan göra ett bättre jobb genom att ha tillgång till en bred uppsättning möjligheter och tekniker (i det här fallet förmågan att programmatiskt manipulera källkod)

Den här typen av AST-manipulation är ett forskningsområde som jag starkt rekommenderar att du fokuserar på (vilket också kommer att ge dig en massiv verktygslåda för din dagliga kodningsverksamhet). Btw, om du följer den här vägen kan du också kolla in O2 Platforms CodeStreams som är en vidareutveckling av MethodStreams-tekniken. CodeStreams ger dig en ström av alla alla variabler som berörs av en viss källvariabel (det som i statisk analys kallas Taint flow analysis och Taint Checking)

Rättelse av kod i realtid (eller vid kompileringstillfället)

Ett annat riktigt häftigt exempel på kraften i AST-manipulationen är PoC:n som jag skrev 2011 om att rätta/kodning av .NET-kod i realtid (i det här fallet Response.Write), där jag visar hur man programmatiskt kan lägga till en säkerhetskorrigering av en sårbar designmetod.

Här är hur användargränssnittet såg ut, där koden till vänster omvandlades programmatiskt till koden till höger (genom att lägga till den extra AntiXSS.HtmlEncode wrappermetoden)

Här är källkoden som gör omvandlingen och kodkorrigeringen (notera rundgången av kod):

Under 2018 är sättet att implementera det här arbetsflödet på ett utvecklarvänligt sätt att automatiskt skapa en Pull Request med de extra ändringarna.

Lämna ett svar

Din e-postadress kommer inte publiceras.