Gödel, Escher, Bach & Microsoft

Så kom dagen hvor Microsofts indbyggede malware-scanner fik et bovskud.

Jeg vil i den anledning gerne reklamere for en bog, en best-seller ligefrem, der udkom i 1979: "Gödel, Escher & Bach"

På meget underholdende og meget pædagogisk vis, viser Douglas Hofstadter at selve ideen i "malware-scan" per defintion er dømt til ikke at virke.

Ikke bare Microsofts, ikke bare "sådan som vi kender det", men som princip kan det ikke virke.

Bogen har mange andre interessante temaer, det er i det hele taget en pragtfuld og klog bog, varmt anbefalet.

phk

Poul-Henning Kamps billede
Poul-Henning er selvstændig systemprogrammør, kernekoder, Varnish-forfatter, data-arkæolog og brokkehoved uden særlig portefølje.

Kommentarer (32)

Torben Mogensen Blogger

Det er ikke kun malware, der ikke med sikkerhed kan fanges. Rice's lov siger, at i et Turing-komplet sprog er enhver ikke-trivielt egenskab af programmers opførsel uafgørligt.

Trivielle egenskaber er dem, som enten alle eller ingen programmer har. For alle andre egenskaber, vil alle "filtre" for disse egenskaber enten slippe "dårlige" programmer igennem eller stoppe "gode" programmer.

For malware-filtre gælder det derfor, at de enten slipper malware igennem eller standser uskadelige programmer.

Hvad kan man så gør ved det? Der er flere muligheder:

  1. Sørg for, at uskadelighed er en triviel egenskab -- hvis ingen programmer i et givet sprog kan være skadelige, kan alle programmer i dette sprog tillades uden risiko.

  2. Brug ikke-Turing-komplette sprog, sådan at skadelighed bliver afgørligt.

  3. Accepter, at dit malwarefilter kan slippe skadelige programmer igennem.

  4. Accepter, at dit malwarefilter kan standse uskadelige programmer.

P.t. lader det til, at model 3 er den mest udbredte, men den er efter min mening også den ringeste. Model 1 og model 4 er meget lig hinanden: Et program accepteres kun som gyldigt, hvis det opfylder bestemte krav. Om disse krav er udtrykt i syntaks, typer eller en efterfølgende statisk analyse betyder mindre. Model 2 begrænser sprogets brugbarhed, men i mange tilfælde er Turing-komplethed overkill, så f.eks. til browser-plugins kunne man godt forestille sig et mere begrænset sprog.

Peter Valdemar Mørch

så f.eks. til browser-plugins kunne man godt forestille sig et mere begrænset sprog

Ideen med at lade plugins bruge hele javascript og så et permissions system og begrænsning af udvalget af API-er er da i denne sammenhæng fin synes jeg.

Har du nogensinde prøvet at skrive en browser-plugin? Hvilke af javascripts sprogegenskaber ville du foreslå at fjerne, der ikke besværliggør eller umuliggør det at skrive browser-plugins?

Troels Henriksen

eval() som en start.

At fjerne eval() er ligegyldigt, da du sagtens kan re-implementere eval() i resten af Javascript.

Jeg tror ikke Torben reelt foreslår at modificere Javascript således at det ikke længere er Turing-komplet. Afvikling i en sandkasse kan ses som en variation over fremgangsmåden med at gøre et sprog uskadeligt per definition, men problemet er at sandkasser er så komplekse, at det ikke altid er tydeligt om de reelt har gjort programmer uskadelige. Faktisk er sandkasser så komplekse, at jeg vil vædde på at de i praksis ikke gør fremmede programmer 100% uskadelige - man finder jo trods alt jævntligt fejl i deres implementering, selvom designet måske godt kan være korrekt.

Torben Mogensen Blogger

Jeg tror ikke Torben reelt foreslår at modificere Javascript således at det ikke længere er Turing-komplet.

Nej, for Javascript er ikke noget godt sted at starte -- et ikke-Turing-komplet sprog, der dels er analyserbart overfor malware, og dels er stærkt nok til at være brugbart, skal designes fra bunden og ikke ved indskrænkning af Javascript eller lignende.

Det er nok nemmere at gøre spørgsmålet trivielt (ved at sikre at ingen programmer kan lave snavs), men det kræver, at snavs og ikke-snavs er tilpas veldefineret til, at man kan udelukke snavs uden at udelukke alt for meget brugbar opførsel. En sandkasse er en måde at gøre dette. Googles Native Client (NaCl) har begrænset x86 maskinkode til dels at bruge en begrænset API og dels gjort indirekte hop og lignende ulovligt, så man er sikret mod hop ud af koden.

Poul-Henning Kamp Blogger

Det er ikke kun malware, der ikke med sikkerhed kan fanges. Rice's lov siger, at i et Turing-komplet sprog er enhver ikke-trivielt egenskab af programmers opførsel uafgørligt.

Hofstadter tager en lidt anderledes vinkel end Turing: Han påpeger at programmer der skal beskytte andre programmer, nødvendigvis selv må beskyttes af et tredje lag af programmer, som nødvendigvis må beskyttes af ...

Poul-Henning Kamp Blogger

Nej, for Javascript er ikke noget godt sted at starte -- et ikke-Turing-komplet sprog, der dels er analyserbart overfor malware, og dels er stærkt nok til at være brugbart, skal designes fra bunden og ikke ved indskrænkning af Javascript eller lignende.

Det "design fra bunden" kaldte man "Java" og man markedsførte det som "et sikkert sprog til browsere" og meget andet vås...

Been there, done that, got the Nets-developed malware to prove it.

Baldur Norddahl

Det "design fra bunden" kaldte man "Java" og man markedsførte det som "et sikkert sprog til browsere" og meget andet vås...

Jeg vil så påpege at et andet design fra bunden som man kaldte "JavaScript" har haft langt færre problemer på den front.

Det er ikke umuligt at specificere og implementere en sandkasse som er rimelig sikker. Der har faktisk ikke været mange fejl i selve sandkasseteknologien i Java. Langt de fleste problemer opstår i det API som Java stiller til rådighed og fortrinsvis fordi kæmpe dele af API'et er implementeret i C udenfor sandkassen. Meget store dele af det C kode kunne have været lave i Java og dermed være beskyttet, men det var (og er) billigere for Sun/Oracle at genbruge C kode. Eksempelvis er java født med support for at komprimere med Zlib og der er intet i det der ikke kunne have været kodet i Java, men det var nemmere at bruge Zlib.

Modsat Java så stiller JavaScript i browsere kun et minimalt API til rådighed. Og dermed er angrebsfladen meget mindre. Man kunne tilmed tænke sig at implementeringen af dette minimale API blev verificeret med formele metoder.

Torben Mogensen Blogger

Det "design fra bunden" kaldte man "Java" og man markedsførte det som "et sikkert sprog til browsere" og meget andet vås...

Vås. Dels er Java Turing-komplet, så stort set alt er uafgørligt, og dels er det ikke designet med sikkerhed som det primære fokus.

Java fik lukket nogle få sikkerhedshuller, f.eks. adressering udenfor arraygrænser, men da et Javaprogram har fuld adgang til filsystemet, og dets kompleksitet gør det umuligt at afgøre, om en specifik brug af filsystemet er sikker, er det på ingen måde et gennemsikret sprog.

Poul-Henning Kamp Blogger

Jep.

Jeg har overvejet at finde nogle brugte eksemplarer i hard-cover.

Jeg ville bruge dem til at slå folk i hovedet med, når de plaprer uinformeret om hvordan alle mulige problemer kan løses med "Kunstig Intelligens" :-)

Martin Kristiansen

Java blev designet fra bunden med sikkerhed for øje - det var bare ikke den slags sikkerhed som markedsføringsafdelingen gik amok over...

Javahypen var stærk i midten/slutningen af 90eren. Var der noget som Java ikke var løsningen på?

Jeg husker især det blev fremhævet at det var lettere at udvikle applikationer i end C++ fordi det ikke havde farlige elementer som multipel nedarvning og templates.

Senere kom generics til Java og nu har vi interfaces med delvis implementation, - ækvivalent med multipel nedarvning af abstrakte klasser i C++.

So the wheels turn.

Jesper Louis Andersen

Googles Native Client (NaCl) har begrænset x86 maskinkode til dels at bruge en begrænset API og dels gjort indirekte hop og lignende ulovligt, så man er sikret mod hop ud af koden.

Tag gerne et kig på WebAssembly. Andreas Rossberg er med i det projekt, og det er ikke helt tosset hvad de har gang i. Ideen er at lave en abstraktion af typisk hardware, men samtidigt begrænse systemet sådan at der er visse dele der er ulovlige.

Første mål har været at få C til at køre og det var ikke helt trivielt fordi C er noget gammel i gårde og derfor har en række konstruktioner der gør det ganske modbydeligt at arbejde med. Dels skal du have gang i relooper-algoritmen. Dels skal du have en shadow-stack fordi C kan tage addresser på stakken og andet uhyrligt. Men det lykkedes og du kan derfor afvikle C i native maskinhastighed inde i din browser nu. Det er pænt fedt.

Desuden er deres stakbaserede system nemt at lave oversættere til, hvilket ikke er helt tåbeligt heller. Lige nu arbejder de på at bygge en ordentlig abstraktion ind i det for bl.a halekald, hvilket åbner døren for stort set alt der arbejder med funktionel kode. Pt lader det til at der er her energien skal sættes ind hvis vi skal slippe for at alt koden i browseren er skrevet i Javascript. At vi kan linke C-klumper ind er virkeligt godt set i forhold til hvor meget velskrevet C kode der nu engang findes derude.

Jesper Louis Andersen

Alt det som udgør en sikkerhedsrisiko ?

Så nemt er det desværre ikke. Gang på gang har vi opdaget hvorledes et system vi fandt sikkert viste sig at have en eller anden lille ting i et hjørne som vi havde glemt at sikre os imod. Problemet er lidt det at dit system skal beskyttes mod alle nuværende problemer, og samtidigt alle fremtidige problemer.

Jeg tror det bedste ville være hvis vi, som Torben siger, lavede en begrænset model og så beviste at denne model har nogen af de egenskaber vi er ude efter. Ikke mindst fordi når vi så finder nye fejl, så kan vi tilføje det som en egenskab til beviset og dermed afvise samtlige programmer der forsøger at snyde. Men der er en temmeligt stor sandsynlighed for at venlige programmer overlever det opstrammede bevis automatisk uden indblanding.

Turing-completeness er ofte den første der bliver skudt når revolutionen kommer.

Poul-Henning Kamp Blogger

Gang på gang har vi opdaget hvorledes et system vi fandt sikkert [...]

Hvem er "vi" og hvad mener "vi" med "sikkert" ? :-)

Jeg tror det bedste ville være hvis vi, som Torben siger, lavede en begrænset model [...]

Jeg tror det ville være langt bedre, hvis datalogerne begyndte at fatte at der er en globaliseret verdensøkonomi involveret i alt hvad de roder med og at den hverken har tid eller evner til at forstå datalogi.

Det samme gælder i andre områder af vores teknologiske samfund, hvor man med meget stort held har reduceret de negative konsekvenser med erstatningsasnvar.

For alle andre produkter end software og religion, ville kunder og brugere af et defekt produkt kunne hive producenten i retten hvis der var forsæt (= Vi vidste det godt men valgte at gøre ingen ting), grov uagtsomhed (= Vi burde have opdaget det og gjort noget) eller konspiration (=Vi tjente penge på at defekten var der), eller falsk markedsføring (= "Fejl er umulige i vores produkt")

Morten V. Christiansen

Uafgørlighed er ikke et problem for malware-scannere, hverken teoretisk eller praktisk. De er designede aggressivt, så de ikke bare standser malware, men også mange programmer, der ikke nødvendigvis er malware, men ligner. Altså Torbens strategi 4.
Svarende til at man slækker på "fidelity" med Hofstadters grammofon. Det betyder af og til at ikke-malware programmer, der f.eks. indeholder malware signaturer, bliver standset. Det kan f.eks. være andre malware scannere.

Morten V. Christiansen

Java blev oprindeligt markedsført som sikkert at bruge i en browser pga. den indbyggede sandkasse, som fjernede adgangen til fil-systemet, operativ-systemet, internettet og andre farlige ting.
Det var for så vidt en ok ide. Desværre begrænsede det også brugbarheden af sproget voldsomt. Så man lavede hurtigt små "huller" i sandkassen, og så gik det meste af sikkerheden væk.
Javas security manager er i dag en stor og kompleks størrelse. Det betyder. at den har været, og formentlig stadig er, fuld af sikkerhedshuller. Og det betyder, at den som regel er håbløs at bruge til ikke-trivielle applikationer. Jeg tror ikke jeg kan komme i tanke om nogen, der bruger den i praksis.
Jeg kan huske, at mit hjerte lige hoppede et slag over, da det i sin tid gik op for mig, at det første java-versionen af NemID gjorde, var at bede brugeren om at slå security manageren helt fra :-) Jeg var ung og naiv.

Jesper Louis Andersen

Jeg tror det ville være langt bedre, hvis datalogerne begyndte at fatte at der er en globaliseret verdensøkonomi involveret i alt hvad de roder med og at den hverken har tid eller evner til at forstå datalogi.
...

Nu kan jeg ikke udtale mig på alle datalogers vegne (specielt eftersom jeg ikke officielt er datalog :P). Men jeg ville umiddelbart tro at de fleste dataloger er ret enige i at software burde omfattes bedre af loven. Specifikt at software har en forventelig opførsel og det ikke er fair at almindelige borgere skal kunne forstå kompleksiteten i de systemer de benytter.

Hvis softwaren korrekthed blev et lovkrav ville mange ting i software skulle gå langsommere og blive dyrere. Det er en god ting. Ikke mindst fordi man så kan begynde at lave systemer som dem Torben skitserer. Lige nu er det bare går-den-så-går-den, og derfor at arbejdet med at sikre et system alt for dyrt i forhold til den gevinst der vindes ved at gøre det.

Baldur Norddahl

Tværtimod er det faktisk hos dataloger jeg finder mest forfærdelse over mit forslag om at leverandører af software naturligvis skal omfattes af helt almindelige regler for produkt- og producent-ansvar.

Det forekommer mig at de værste er hardware producenter. Du kan rimeligvis regne med et vist niveau af opdateringer til dit operativsystem. Men din router, billige Android telefon, dit online kamera, din bil* ? Glem det. De dimser er som den dag de blev købt til du kasserer dem, uanset hvor mange fejl der måtte findes undervejs.

*) Hvis ABS softwaren fejler bliver det fikset, men hvis man kan bryde ind i bilen med en bluetooth dims, så er det dit eget problem.

Fritz Henglein

Der findes fundamentale naturlove om hvilke problemer, der kan beregnes -- og ikke kan beregnes; hvor mange ressurser de kræver at løse som minimum; hvordan man, for klasser af problemer, kan automatisk generere ressurseoptimale løsninger, etc. Teorien om det, beregneligheds- og kompleksitetsteori, er udviklet siden 30erne, hhv. 70erne. Rice's Theorem er et eksempel; konstruktion af computervira via Kleene's rekursionsteorem en anvendelse. Men det er ikke (eller kun i minimal grad) pligt- eller valgfrit pensum nogen steder i Danmark, selv på datalogiuddannelserne. Det er lidt som at studere fysik uden kvantemekanik...

Bente Hansen

Gælder vel for det meste, og man kan ikke fraskrive sig ansvar.

At vi har levet med, meget dårlige software, især fra kommercielle firmaer som MS. Som har udgivet software, langt tid før det var klar, med gentagen lovning om sikkerhed, guld og grønne skove, i hver version.
Er vel også en fejl af os som forbruger, og manglende opbakning fra politisk side, til at få helt styr på juraen, samt hjælp til sagsanlæg.

Med software, sammenkøbt med hardware er dækket. Og her burde forbrugerombudsmanden stå i kø for at hjælpe når-

Der ikke kommer opdatering til Andrid inden for den 18 måneders garanti periode, som producenter har lovet Google.

At Windows Telefoner kan leveres tilbage, når de lovet opdateringer ikke kommer.

Computer/Bærbare/Tablet leveres tilbage når de har fejl, også når det gælder softwaren, som her med sikkerhedshuller.

IoT Enheder med standard kodeord, og uden softwareopdateringer, også leveres tilbage, under købeloves 2 års garanti. Det virker ikke, da andre kan tilgå det.

Sælgeren har da de maximale 2-3 uger til at rette problemet. men det betyder vel også at hver gang at der er lavet en rettelse, som med en Windows opdatering eller en ny firmware. Så udvides garantien med yderligere 2 år.

Jeg kan ikke se at der ikke i den bestående lov, især i de lande i EU som har en bedre persondatalov og forbrugerbeskyttelse. Ikke vil være muligt at tilbagelevere et samlet defekt produkt, og bede om at få det lavet.

Log ind eller opret en konto for at skrive kommentarer