Aligraafien louhinta tietämysverkostosta : Ilmiöiden paikantaminen epätäydellisillä tiedoilla

Abstract

Tässä diplomityössä tutkitaan olemassa olevan PINGS-algoritmin (Procedures for INvestigative Graph Search) soveltuvuutta kuvattujen ilmiöiden paikantamiseen geneerisestä tietämysverkostosta. Tietämysverkosto on graafi, joka kuvastaa kaikkia asioita ja asioiden välisiä yhteyksiä mitä tiedetään tarkasteltavasta kokonaisuudesta. Löydöksiä paikannetaan kuvaamalla kyselygraafi algoritmille. Kyselygraafi esittää ilmiön tietämysverkoston pienenä aligraafina, jolle halutaan löytää vastineita tietämysverkostosta. Kun tietoaineistosta tehdään haku, saadaan vastauksena samankaltaisia mutta ei välttämättä täydellisesti hakua vastaavia osumia. Alkuperäisen PINGS-algoritmin on kehittänyt Muramudalige et al.

Aluksi perehdytään alkuperäiseen PINGS-algoritmin toteutukseen sekä todetaan algoritmin toimivuus saatavilla olevien tietojen perusteella. Algoritmia kokeillaan alkuperäisten tekijöiden kehittämällä tietoaineistoilla.

Työn valmisteluvaiheen edetessä huomataan, että julkisesti saatavilla oleva ohjelmakoodi ei sellaisenaan toimi, joten tutkimustyön tekemistä varten toteutetaan algoritmin kuvausten perusteella PINGS-algoritmia noudattava lähdeaineistoriippumattomampi algoritmi. Geneerisen käsittelykyvyn arviointia varten luodaan keinotekoinen tietämysverkosto, joka koostuu tietokoneista, verkoista sekä haavoittuvuuksista. Kehitetty verkosto on rakenteeltaan kompleksisempi ja monipuolisempi kuin alkuperäisten tutkimusartikkelien testiaineisto.

Työn tuloksena todetaan, että PINGS-algoritmi voi karkeasti soveltua käyttäjän kuvaamien ilmiöiden louhimiseen geneerisestä epätäydellisestä tietämysverkostosta, mikäli toteutuksessa otetaan huomioon tässä tutkimuksessa kokeiltuja ja esitettyjä korjauksia.

Lopputuloksena algoritmin avulla voidaan paikantaa haavoittuneet, yhteenliitetyt tietokoneet sekä niiden väliset yhteydet. Lopuksi esitetään ehdotuksia jatkotutkimukselle sekä parannusehdotuksia algoritmin jatkokehitykselle.

I detta diplomarbete undersöks hur den existerande PINGS-algoritmen (Procedures for INvestigative Graph Search) tillämpar sig för minering av beskrivna fenomen ur en generisk kunskapsgraf. En kunskapsgraf är ett nätverk av information som beskriver alla saker och förbindelser vad man vet om någon helhet. Fynden finner man med att beskriva det eftersökta fenomet med hjälp av ett frågediagram. Frågediagrammet representerar en subgraf vi vill finna i kunskapsgrafen. När man frågar kunskapsgrafen med ett frågediagram får man som resultat likadana subgrafer men inte nödvändigtvis exakta representationer av frågan. Den ursprungliga PINGS-algoritmen är utvecklad av Muramudalige et al.

Först studerar vi den ursprungliga PINGS-algoritmens implementation och konstaterar dess funktionering med hjälp av tillgänglig information. Vi provkör algoritmen med den allmänt tillgängliga datauppsättning som de ursprungliga utckeclarna producerat.

Under arbetets preparationsfas märker vi att den allmänt tillgängliga algoritmens källkod fungerar inte som sådan med generisk material. Vi besluter oss för att implementera en mer generiskt kapabel PINGS-algoritm med att följa informationen i källmaterialet. För att testa algoritmens funktion i generisk problemlösning, skapar vi ett syntetiskt kunskapsnätverk som består av datorer, nätverk och sårbarheter. Det syntetiska nätverket är mer kompleks och heterogen till struktur jämfört med källmaterialets exempelstudie.

Som resultat av detta arbete konstaterar vi att PINGS-algoritmen kan på grov nivå tillämpa sig till att minera beskrivna fenomen ur ett icke perfekt kunskapsnätverk. För en bättre prestation krävs dock att man tar i beaktande förbättringar som provas och presenteras i denna studie. Slutresultatet är att vi kan finna sårbara datasystem och förbindelser i ett nätverk. I sammandraget beskrivs också förslag till vidare studier och förbättring samt vidareutveckling av algoritmen.

In this thesis we study how the existing PINGS-algorithm (Procedures for INvestigative Graph Search) can be used for finding described phenomena in a generic knowledge graph. The knowledge graph represents all identified entities (nodes) and connections (edges) that we assume to know about something as a network. We identify candidates, subgraphs, by describing the phenomena as a query graph. The query graph is a small representation of known entities and connections we assume to at least partially match. As we query the knowledge graph using the query graph, the result can contain similar but not necessary exact matches. The original PINGS-algorithm is developed by Muramudalige et al.

First, we study the original PINGS-algorithm and test the functionality on the basis of available information. We test the algorithm with a dataset that is created by the original developers and presented in the cited articles.

During the study, we realize that the publiced source code of the PINGS-algorithm doesn't work as such for the intended purpose. We decide to re-write the algorithm following the published articles and documentation to make the algorithm work for our knowledge graph. For evaluating the algorithm suitability for our case, we develop a synthetic knowledge graph consisting of computers, networks and vulnerabilities. This synthetized netowrk is more heterogenous of nature compared to the original material.

As a result of this work, we manage to find vulnerable computers and connections in the synthetic network. We discover that the PINGS-algorithm can roughly fit the purpose of mining described phenomena from an generic incomplete knowledge graph. We describe identified and proposed improvements and proposals of continued study that can improve the algorithm and similar solutions.