2008-07-06

Varför FRA's filter inte kan funka, rent matematiskt.

Hittade en intressant länk via en av kommentarerna på moderaten GöranPettersons blogg

Den handlade om problemen med falska träffar när man letar efter ovanliga saket i stora material. Via den kom jag till en wikipediaartikel som beskrev den ganska simpla matematiken runt det.

Och denna simpla matematik gör att man faktiskt med gott fog kan påstå att det där med att hitta relevant information med filter, så som FRA påstår att de ska göra, är väldigt mycket svårare än vad man vid första anblicken kan få för sig.

Det är nämligen så att om man filtrerar ett väldigt stort material, och letar efter något som är ganska ovanligt, så ger minsta lilla osäkerhet i filtrets exakthet jättelika utslag i form av falska träffar, sånt som signaleras som träff fast det egentligen inte är det. Och falska träffar i det här fallet, det är din och min privatkorrespondens.

Exempel:

Låt oss säga att 100 miljoner meddelanden passerar FRA per dag, det är lågt räknat om man med meddelande menar IP-Paket.

Låt oss också anta att 1 meddelande per 10 miljoner har sådant innehåll att det ska fångas, och att filtret är korrekt i 99% av fallen.

Då blir det så här (Och detta är inget tyckande, det är bara ren matte):


Parametrar:






Antal genomsökta meddelanden:


100 000 000


Filtrets korrekthet:


99%


Förekomst av meddelanden som bör fångas in 1 per:


10 000 000


















Resultat:






Antal meddelanden som korrekt släpps förbi:


98 999 990,1









Antal meddelanden som felaktigt fastnar i filtret:


999 999,9









Antal meddelanden som korrekt fastnar i filtret:


9,9









Antal meddelanden som felaktigt släpps förbi:


0,1









Detta betyder att endast 10 meddelanden per 1 miljon infångade är sådana som man vill fånga!

(De andra är sådant som FRA inte har med att göra.)

För varje korrekt infångat meddelande ska alltså FRA läsa igenom 100 000 felaktigt infångade som filtret bedömt relevanta, men som inte är det.

Hur mycket folk ska de anställa egentligen...?


Matten är jätteenkel, se wikipediaartikeln: http://en.wikipedia.org/wiki/False_positive_paradox

För den som vill testa med egna värden finns ett kalkylark på google documents


Andra om: , , , , , , ,

23 Comments:

Anonym said...
Den här kommentaren har tagits bort av bloggadministratören.
JorgenL said...

Tog bort en "off topic" spamkommentar från anonym. Om du ska kommentera, kommentera inlägget...
Min gräns är dessutom lägre för anonyma...
Vill du skiva nåt allmänt, skaffa en egen blogg...

Kristofer S said...

Intressant räkneexempel, men varför räkna med 99 %? Vad är grunden till det antagandet? Det är ju en väldigt grov siffra, är inte 99,99 % eller ännu högre mer ackurat och närmre verkligheten i detta sammanhang?

JorgenL said...

@Kristofer:
99% är nog redan i sig ett överdrivet högt värde.

Baserat på mina erfarenheter som programmerare/systemerare sedan 30 år, så vet jag hur oerhört svårt det är att få ut nåt vettigt ur information som inte är skapad med just ett specifikt syfte. Sätter man villkoren så tight att man bara får med sånt som man vill så missar man det mesta av intresse, gör man inte det så blir man dränkt av ointressant information.

Om man kör samma exempel som ovan med 99,99% träffsäkerhet så får man 1000 felträffar / riktig, vilket fortarande är osannolikt att man ska kunna hantera.

Det är dock helt orealistiskt att man ska kunna skapa filter som bara gör fel en gång på tusen, imho.

Björn Wadström said...

Bra med mattelektion. Hoppas Björklund läser.
Men lite ilseledande blir artikeln om man förstår vad spaning handlar om.
FRA-lagens syfte är att staten skall kunna kartlägga dina vanor. Genom att se att du passerar ett antal uppsatta kriterier så fastnar du. Besöker vissa sidor,läser samhällskritisk press, har vissa sexvanor, ringer vissa platser, tider osv. osv.
Att bygga upp kriterierna är en vetenskap i sig. Men som alltid bygger det på fantasier. I annan vetenskap pratar vi om hypoteser. När det gäller signalspaning handlar det om rena gissningar som kan grundas på vad som helst.
Så när någon fastnat avlyssnas allt från den individen.
Det går heller inte att försvara sig mot de bilder som produceras eftersom kriterierna inte är kända och det går inte att objektivt upprepa analysen.

Jo jag besökte en islamistisk sida och en nationalistisk sida. Ja jag tittade på en kartbild via google. Jo jag kör en HD och ringde klockan tre på natten...Men va fan inte betyder det att rakkrämen i påsen.......
1984, Stalin, Hitler.. alla dessa liknelser människor gör är inte fel. De gör som FRA tittar på kriterier och kommer fram till att Reinfeldt och Björklund leder oss in i en diktatur...eller åtminstände att de blir av med sin integritet och frihet.
FRA ska vi inte ha!

JorgenL said...

@Björn:
Matematiken funkar även för trafikdatastatistik.

Även den är otroligt omfattande så även där måste man med nån slags filtermekanism sålla fram det som är intressant, och även i det fallet kommer man att få oerhört många fler orelevanta träffar är relevanta.

Anonym said...

Som ett komplement till denna diskussion vill jag bara tippsa om ett utmärkt inlägg “CIA och Bruce Schneier – Varför FRA lagen INTE KOMMER ATT FUNGERA!” på http://uddebatt.wordpress.com/.

Källorna är alltså CIA och Bruce Schneier (”säkerhets guru”) som på ett mycket bra sätt förklarar varför det hela INTE kommer att fungera även om man vill att det skall fungera och tekniken finns.

Erik

David J said...

Tack för ditt stöd i den här diskussionen!

Får jag lägga in delar av det du skrivit här i FRApedia-artikeln? (Eller så kan du göra det själv så vet du att det blir korrekt.)

tw said...

"In the anxious months after the Sept. 11 attacks, the National Security Agency began sending a steady stream of telephone numbers, e-mail addresses and names to the F.B.I. in search of terrorists. The stream soon became a flood, requiring hundreds of agents to check out thousands of tips a month.

But virtually all of them, current and former officials say, led to dead ends or innocent Americans."

http://www.nytimes.com/2006/01/17/politics/17spy.html

Andreas said...

Som jag skrev i ett eget inlägg förstår jag inte hur man ska få fram något överhuvudtaget, men om det trots allt går så kan det finnas ett användningsområde; nämligen data mining. Ingen aning om hur det funkar i praktiken men det är iaf till för just stora datamängder och det är just vad staten hävdar att datan inte ska användas till...

JorgenL said...

@Erik:
Intressanta saker, både CIA's bok och Schneiers artikel. Jag antar att FRA hävdar att man är medvetna om problemen som behandlas i CIA boken, och att deras utmärkta medarbetare tar hänsyn till detta när de spanar...

Schneier fokuserar mera på konkret brottsprevention än vad FRA's uppdrag är sagt att vara, men det gör ju inte att hans resonemang inte stämmer i de delar som handlar om att hitta rätt saker att observera, och den oerhörda mängden "false positives"

@DavidJ:
Använd vad du vill, jag förespråkar fri ickekommersiell användning.. :-)

@Andreas:
Datamining är väl ungefär det FRA har använt sin Titandatabas med trafikdata till. Det som är problemet där som överallt annars är att veta vilka frågor man ska ställa. Datamining är en oerhörd fälla i många fall eftersom man väldigt lätt får de svar man letar efter, sas. Om man inte har klart för sig exakt vad som skiljer "normalt beteende" från "onormalt" så hjälper inga sådana system, man får lik förbaskat bara en massa irrelevant information.

Vissa saker kanske går att identifiera den vägen, men i det stora hela faller det på att även en stor del "normala" användare beter sig på ett "onormalt" sätt och de är så många fler än de som man faktiskt vill hitta att de överskuggar dessa. Återigen "the false positive paradox"....

Anonym said...

Hej.

Förmodligen söker inte FRA på enskillda ord, eller liknande. Prova att i stället för att bara gissa vilt använda matematiken som du hittar på http://en.wikipedia.org/wiki/Bayesian_spam_filter.

FRA har själva sagt att de lagrar relationsdata, vem som har varit i kontakt med vem. Hur folk tar kontakt med varandra och på vilket sätt de håller kontakten (sporadiskt, sedan börjar ALLA i "cellen" skicka massor med meddelanden till varandra helt plötsligt = strax dags för ett nytt dåd) kan ge indikationer på vad för slags sällskap det handlar om.

Vad har du för källor?

JorgenL said...

@Anonym(00:50):
FRA söker enligt egna uppgifter på väldigt komplexa kombinationer av sökbegrepp, om de använder Bayesisk filtrering eller inte är inte känt. Problemet för dem att göra det skulle vara att det är en form av självlärande algoritm, så man måste mata den med meddelanden som ska fångas resp inte ska fångas, för att få den att lära sig hur man skiljer dessa åt. Eftersom man inte har en lista med autentiska meddelanden som ska fångas lär det bli svårt. I vilket fall är det knappast möjligt att med den typen av algoritmer få upp en tydlig skillnad mellan sånt som ska fångas och sånt som inte ska fångas, precisionen blir helt enkelt inte tillräckligt bra, speciellt i ljuset av det som blogginlägget diskuterar.

Problemet med exemplet du tar om trafikdata är att en förskräcklig massa "normala" användare också uppför sig prcis på det där sättet som du beskriver. Plötsligt börjar en grupp människor skicka en massa mail till varandra.

Hur många kompisgäng i Sverige börjar plötsligt skicka mail till varandra på en fredagseftermiddag?
Jämfört med hur många terroristceller finns det i Sverige?

Det är ju det som är kärnan i "the false positive paradox" att det man söker efter är väldigt sällsynt i förhållande till det "normala"

Vad gäller källor så är det egentligen bara wikipediaartikel om "the false positive paradox", resten är antaganden om rimliga kommunikationsvolymer. De enda som är avgörande för utfallet är frekvensen av meddelanden som SKA fångas och träffsäkerheten på filtret, resten är rent logiskt resonemang.

Uppskattningen 1 meddelande per 10 miljoner som bör fångas är en ren gissning som bygger på att skummisar kommunicerar som folk i allmänhet. Om vi har 4 miljoner internetanvändare i Sverige + ett antal servrar som accessas utifrån av nån miljon användare utomlands + en mängd automatiserade meddelanden + stora filöverföringar som fyller ut bandbredd, så känns det som rimligt att anta att en 10 miljontedel av denna bandbredd kan tänkas utgöra trafik som borde skulla avlyssnas.

Vad gäller säkerheten på filtret så är det ett antagande som är avsett att vara kraftigt överdrivet åt det säkra hållet, jag tror egentligen inte det finns en chans att skapa så bra filter.

Sven Höckert said...

Mycket intressant inlägg i debatten om signalspaning.

Det värsta är inte att min mejl kan bli läst av en människa.

Det värsta är att en sökrobot fångar upp min mejl genom ett dataprogram av diverse variablar och på så sätt bedömer mig som ett yttre hot eller inte.

Var finns humanismen i detta? Vi kan bara hoppas att vi ALDRIG glömmer bort det medmänskliga.

Jag och du och alla vi vill ju leva i fred och frihet.

Andréas said...

Det är ju ingen tvekan om att det är hopplöst att skapa ett filter som bara gör fel en gång per tusen.

För de som inte är informations- eller systemvetare är precisionsvärdet antalet relevanta träffar dividerat med det totala antalet träffar och recallvärdet är antalet relevanta träffar dividerat med samtliga relevanta dokument i samlingen.

Eller om man så vill; med en sökalgoritm får du fram tio träffar varav fem är relevanta. Precisionsvärdet är då 5 / 10 = 50 %. Totalt i samlingen finns det tjugo relevanta dokument. Recallvärdet blir alltså 5 / 20 = 25 %.

För att ta en enkel liknelse blir det ungefär som när man själv söker på Google.
Är man för bred i sin sökning sjunker precisionen, men recall ökar.
Är man för smal i sin sökning ökar precisionen, men recall sjunker.

Nu återstår då problemet Jörgen redogjort för; de kommer att få mängder med falska positiva träffar. Detta är helt oundvikligt såtillvida att de inte vill sänka sitt recallvärde till i princip noll och intet.

Enligt uppgift ska det finnas drygt 250 000 ord i stopplistan. Frågan är om det räcker att skriva 'bomb', 'Rosenbad', 'korståg' i sitt mail för att deras filter ska larma. Min gissning är att det inte gör det. Främst därför att det förefaller mig vara osannolikt att någon skulle skriva så öppet i ett vanligt mail om en sådan sak. (Det brukar ju sägas att man inte ska skriva i ett okrypterat mail något man inte skulle skriva på ett vykort.)

Fast om det inte larmar för en sådan sak; vad larmar det då för?

Mumfi said...

(Hej) Intressant postning. Inom medicinen så brukar man lösa det genom att man regelmässigt testar positiva resultat med ett annorlunda test. Så när du väl får besked om att du är HIV-positiv är du antagligen körd...

Hur som helst, jag tror att premissen är lite felaktig. Naturligtvis vet FRA om allt detta, jag måste, trots indikationer på motsatsen, utgå från att de inte är idioter allihopa. FRA har inte för avsikt att för sina kunders räkning fånga upp någonting över huvud taget specifikt. Vad man gör är att man dels ritar relationsgrafer, dels spanar på stora trender. Exempelvis skulle man från regeringens sida, om man haft FRA-systemen på plats redan, förstått att inte ta FRA-frågan nu utan vänta till man kunnat smyga igenom den på ett lämpligt sätt. Att göra en graf över alla bloggare som upprörs över FRA är inte svårt, att sedan vänta tills besöksstatistiken på sagda bloggar går ner är lätt. Mäta referenser till bloggarna i fråga i e-mailtrafiken kanske? Kontrollera hur mycket av e-mailtrafikten som relaterar till frågan... o.s.v. Falska positiver är inte ett stort problem i sådana förehavanden.

Det är som ett super-SIFO. Ett SIFO som folk inte ljuger för. Omedelbara kundundersökningar med ett enormt, om inte nödvändigtvis representativt, underlag! Skulle jag suttit i regering hade jag antagligen dreglat av bara tanken. Som rättshaverist med anarkistiska tendenser ser jag naturligtvis möjligheten att nyttja ett sådant system för mina egna syften! Man kan uppnå mycket genom att få staten att tro att opinionen ligger åt ett visst håll.

För övrigt: Skulle jag varit terrorist, vilket FRA antagligen tror, du med nu eftersom jag postar på din blogg, så skulle jag gömma data i jpg-filer och lägga ut dem på flicker. Eller värre mp3 varefter jag spred dem i fildelningsnätverken.

JorgenL said...

@mumfi:

Absolut, den typen av information går säkert att hämta in, men den har ju inte speciellt mycket med yttre hot att göra, och den skulle till stor del dessutom kunna göras rakt av på internet utan att gå in och tappa kabeltrafik. Inte med riktigt samma precision, men ändå.

Skillnaden är ju att man då söker efter väldigt specifika saker, inte efter allmänt "misstänkta" saker. Det de påstår är ju att de ska kunna "identifiera hot", dvs hitta sånt som är tidigare okänt genom allmän trålning, och det är det jag egentligen kritiserar i postningen.

Det argument som har använts av förespråkarna är ju att det hela på nåt sätt ska ge ett konkret skydd, dvs kunna förutsäga konkreta hot, och det är knappast nåt man gör genom en hemlig opinionsundersökning.

Eller kan vi ha missuppfattat alltihop, det kanske bara är för att ha "opinionsundersökning-at-your-fingertips" för regeringen det handlar om?

Fast knappast ens det kommer väl att funka nu när folk börjar bli medvetna om att den här risken finns. Jag använder konsekvent https på alla ställen där det går, och såvitt känt så finns det väl inga enkla sätt att knäcka den?
Och skulle jag diskutera nåt som är reellt intressant för statsmakten så skulle jag köra det med GPG och det tror jag väl är ganska väl spritt vid det här laget...

Fast din ide om att manipulera statsmakten är inte dum alls, problemet är ju att få det att se ut som att det är många olika som yttrar sig, man kan ju inte skicka allt från sin egen IP...

Mumfi said...

@jorgenl Uppenbart är det en skillnad på vad de säger att man ska ha systemet till och det enda vettiga man faktiskt kan ha ett sådant system till.

Anledningarna till att man vill tappa trafik är antagligen att man vill bygga upp relationsgrafer, som sagt, samt bättre precision. Med relationsgrafer till sitt förfogande kan man dessutom med dessa som parameter förfina sökresultaten ytterligare genom att helt enkelt bara spana med filter på de man redan misstänker. Då höjer du den där parametern i din formel där du anger förekomsten av det man söker efter i underlaget, som ändå är det viktigaste om man ska få ett hanterbart resultat.

Sedan ska vi inte glömma möjligheterna att sätta dit alla dedär som myndigheterna _vet_ är terrorister men där de inte har bevis... Liter specialspaning från FRA så är alla misstänkta, speciellt om metoderna är hemliga. Det är svårt att för en hemlig domstol förklara att man är oskyldig till anklagelser man inte får veta om när SÄPO säger att FRA säger att deras dator säger att man antagligen är det, fast ingen säger det till dig eller din advokat.

Som någon sa ovan, ska du ha rakkräm med dig till jobbet, se till att ha det nu innan FRA har sina register på plats. Nästa gång kommer du att ha terroristkopplingar. Om inte annat för att motivera alla hemliga organisationers budget. Jag tycker att det varit förvånansvärt lite snack om vätskeförbudet till exempel. Vi har här ett antal 25-åringar som talat hypotetiskt på en öppen chat om en orealistisk plan. Helt plötsligt så får man inte ta med vätska på flyget? TATP är ett PULVER! Några andra flytande sprängämnen har jag inte hört talas om. Nitroglycerin tillverkar man inte på plats... Ingen av "terroristerna" hade köpt en flygbiljett, bara en av dem hade pass. Jag tycker det låter som ett sätt för engelska signalspaningen att motivera sin budget.

Det där är föresten den största risken med offentliga spioner, de måste motivera sin existens. Då är det bättre med hemliga sådana.

Ett annat litet problem är att ett verktyg som det här i henderna på en regering betyder att regeringsbyten blir något mycket sällsynt. Småpartier som miljöpartiet skulle aldrig få tillfälle att uppstå osv etc.

JorgenL said...

@mumfi:

Tyvärr kan det nog tänkas att du har rätt...

Jag brukar alltid avfärda konspirationsteorier med Hanlons rakkniv: "Tillskriv aldrig något ont uppsåt när det är tillräckligt att förklara det med dumhet", men i det här fallet förklarar det nog bara politikernas agerande, inte FRA's...

aa said...

De kommer börja med att selektera fram trafik från relevanta källor som till exempel diplomati eller storindustri. Dessutom är volym- och frekvensanalyser ett viktigt signalspaningsverktyg. På FRA vet man vad man gör. Det är i riksdagen och Rosenbad man inte gör det.

JorgenL said...

@aa:
Frågan är om man ska vara mer eller mindre oroad av det...

Lutar nog trots allt åt mer. Kunniga människor som föser okunniga framför sig är nog farligare.

Anonym said...

Naturligtvis är det enkelt att skapa "filter med 100 % säkerhet! Jag har gjort en mycket enkel beskrivning på ett mycket enkelt "filter" på:
http://www.sourze.se/FRA_vs_avpersonifierad_signalspaning_10651073.asp

Men det är möjligt att vi menar olika saker med ordet "filter". Vad jag menar är att det är enkelt att hitta det som satisfierar sökbegreppen.

JorgenL said...

@anonym (Uno?):
Det är klart att det hårdvarumässigt går att filtrera ut visst material rent tekniskt, men att göra det baserat på innehåll, dvs kunna klassificera innehållet som "relevant för hotbilden mot sverige" låter sig inte göras med automatik.

Ett filter som gör det låter sig inte konstrueras på ett sätt så att det i den totala dataströmmen returnerar annat än en bråkdel korrekta träffar.

Din ide med hårdvarumässigt framräknad statistik är säkert användbar för statistiska förekomster av sökbegrepp, men det kan inte säga något om i vilken BETYDELSE de används.

Det innebär att statistiken man får ut är lika förorenad av "false positives" som meddelandena i sig, och det blir mycket små skillnader mellan "normalt" läge och "avlyssningsindikerat" läge.

Om man optimistisk skulle förutsätta att snittrelationen mellan "true positives" och "false positives" är 1 mot 1000, så hur skulle man kunna urskilja vid vilka tillfällen avlyssning ska tillåtas?