Analys av ett probabilistiskt system kräver ofta att lära sig den gemensamma sannolikhetsfördelningen av dess slumpmässiga variabler. Beräkningen av den exakta fördelningen är vanligtvis en uttömmande exakt analys av alla utföranden av systemet. För att undvika den höga beräkningskostnaden för en sådan uttömmande sökning, har statistisk analys studerats för att effektivt få ungefärliga uppskattningar genom att analysera endast en liten men representativ delmängd av systemets beteende. I detta dokument föreslår vi en kombinerad statistisk skattningsmetod som kombinerar exakta och statistiska analyser för att uppskatta ömsesidig information, Shannon entropi, och villkorlig entropi, tillsammans med deras konfidensintervall. Vi visar hur man kombinerar analyserna på olika komponenter i ett diskret system med olika noggrannhet för att få en uppskattning för hela systemet. Den nya metoden utför viktad statistisk analys med olika provstorlekar över olika komponenter och finner dynamiskt sina optimala provstorlekar. Dessutom kan det minska provstorlekarna genom att använda förkunskaper om system och en ny abstraktion-samplingsteknik baserad på kvalitativ analys. För att tillämpa metoden på källkoden för ett system, visar vi hur man sönderdela koden i komponenter och bestämma analysmetoden för varje komponent genom att överblicka genomförandet av dessa tekniker i HyLeak-verktyget. Vi visar med fallstudier att den nya metoden överträffar den senaste tekniken när det gäller att kvantifiera informationsläckage. 168 F. Biondi m.fl. om system, inklusive abstraktion-då-provtagning teknik med kvalitativ analys. I avsnitt 6 visas den optimala fördelningen av prov till komponenter som ska vara statistiskt prov för att förbättra uppskattningens noggrannhet. I avsnitt 7 ges en översikt över genomförandet av teknikerna i HyLeak-verktyget, inklusive hur man sönderdelar källkoden för ett system i komponenter och bestämmer analysmetoden för varje komponent. Avsnitt 8 utvärderar den föreslagna metoden och illustrerar dess effektivitet mot den senaste tekniken, och Sect. Nio avslutar dokumentet. Detaljerade bevis finns i bilaga A. Den informations-teoretiska metoden för programsäkerhet går tillbaka till Denning [Den76] och Gray [III91]. Clark och Al. [CHM01, CHM07] presenterade tekniker för att automatiskt beräkna ömsesidig information om ett tvingande språk med loopar. För ett deterministiskt program kan läckage beräknas från ekvivalensförhållandena på hemligheten framkallad av de möjliga utgångarna, och sådana relationer kan automatiskt kvantifieras [BKR09]. Under- och över- approximation av läckage baserat på observation av vissa spår har studerats för deterministiska program [ME08, NMS09]. Som ett tillvägagångssätt utan att svara på informationsteori McCamant et al. [KMPS11] utvecklade verktyg som implementerar dynamiska kvantitativa analystekniker för säkerhet. Fremont och Seshia [FS14] presenterar en polynomalgoritm för att uppskatta vikten av spår av deterministiska program med möjlig tillämpning på kvantitativt informationsläckage. Framsteg i randomiserad programanalys inkluderar en skalbar algoritm för enhetlig generering av prov från en distribution definierad som begränsningar [CFM + 15, CMV13], med applikationer för begränsad slumpmässig programverifiering. Det statistiska tillvägagångssättet för kvantifiering av informationsläckage har undersökts sedan Chatzikokolakis et al. [CCG10]........................................................................................................... Chothia m.fl. har utvecklat denna metod i verktyg läckaiEst [CKN13, CKNa] och LeakWatch [CKN14, CKNb]. Den statistiska hybridmetoden i detta papper kan betraktas som en förlängning av den, med införandet av viktning av komponenter och adaptiva tidigare behandlingar som inspirerats av vikten av provtagning vid kontroll av statistiska modeller [BHP12, CZ11]. Såvitt vi vet har inget tidigare arbete tillämpat viktad statistisk analys på uppskattningen av ömsesidig information eller andra läckagemått. Idén om att kombinera statiska och randomiserade tillvägagångssätt för kvantitativt informationsflöde föreslogs först av Köpf och Rybalchenko [KR10] medan vårt tillvägagångssätt bygger på statistisk uppskattning för att ha bättre precision och noggrannhet och är tillräckligt allmänt för att hantera probabilistiska system under olika tidigare informationsförhållanden. Inom relaterade områden har hybridmetoden som kombinerar exakt och statistisk analys visat sig vara effektiv, till exempel i konkolisk analys [MS07, LCFS14], där det visas att indata som genereras av hybridteknik leder till större kodtäckning än indata som genereras av både helt slumpmässig och konkolisk generering. Efter offentliggörandet av den preliminära versionen [KBL16] av detta dokument har några dokument om kvantitativt informationsflöde som kombinerar symboliska och statistiska metoder publicerats. Malacaria m.fl. [MKP + 18] presenterar en metod som utför Monte Carlo provtagning över symboliska vägar medan de tidigare distributionerna är begränsade till att vara enhetliga. Söta et al. [STS + 18] kombinera abstraktion tolkning med provtagning och konkolisk utförande för resonemang om Bayes sårbarhet. Till skillnad från vårt arbete syftar dessa två studier till att endast ge gränser för informationsläckage och inte använda statistiska hypotestester. Vårt verktyg HyLeak behandlar ett enkelt och tvingande språk som är en förlängning av det språk som används i QUAIL-verktyget version 2.0 [BLQ15]. De algoritmer för exakt beräkning av informationsläckage som används i detta dokument är baserade på spåranalys [BLMW15], som genomförs i QUAIL-verktyget [BLTW, BLTW13, BLQ15]. Som påpekats ovan, QUAL-verktyget genomför endast en exakt beräkning av läckage som undersöker alla utföranden av program. Därför prestanda av QUAL inte skala, särskilt när programmet utför komplicerade beräkningar som ger ett stort antal exekvering spår. QUAL:s resultat jämfört med HyLeak representeras av den "precisa" analysmetoden i Sect. 8. Vad är det som händer? Eftersom QUAL inte stöder det statistiska tillvägagångssättet eller hybridmetoden, kan det inte hantera stora problem som HyLeak kan analysera. Som påpekats ovan har de stokastiska simuleringstekniker som införts i HyLeak också utvecklats i verktygen LeakiEst [CKN13] (med dess förlängning [KCP14]) och LeakWatch [CKNP13, CKN14]. Dessa verktygs prestanda jämfört med HyLeak representeras av den "statistiska" analysmetoden i Sect. 8. Vad är det som händer? Verktyget Moped-QLeak [CMS14] beräknar ett programs exakta informationsläckage genom att omvandla det till ett algebraiskt beslutsdiagram (ADD). Som anges i [BLQ15] är denna teknik effektiv när programmet under analys är tillräckligt enkelt för att omvandlas till ett ADD, och misslyckas annars även när andra verktyg, inklusive HyLeak, kan hantera det. I synnerhet finns det enkla exempel [BLQ15] där Moped-QLeak misslyckas med att producera något resultat men som kan undersökas av QUAL och LeakWatch, därav av HyLeak. Många verktyg för informationsläckageanalys begränsade till deterministiska indataprogram har släppts, inklusive TEMU [NMS09], squifc [PM14], jpf-qif [PMTP12], QILURA [PMPd14], nsqflow [VEB + 16] och Steg 1: Förbehandling Steg 1a. Lexing, tolkning och syntaxkontroll. HyLeak inleds med lexikal analys, makrosubstitution och syntaxanalys. I makrosubstitution ersätts konstanterna som definieras i inmatningsprogrammet med deras deklarerade värden, och enkla operationer löses omedelbart.
Inom forskning om integritet presenterar några papper (t.ex. REF ) hybridmetoder som kombinerar symboliska och statistiska analyser för att kvantifiera integritetsläckage.
Hybrid statistical estimation of mutual information and its application to information flow
{'venue': 'Formal Aspects of Computing', 'journal': 'Formal Aspects of Computing', 'mag_field_of_study': ['Computer Science', 'Mathematics']}