Grafy. To nie tylko łączenie kropek kreskami :)

Przeglądając Internet każdy z nas na jakimś etapie natknął się na wizualną reprezentację grafu. Takie kółeczka (właściwie wierzchołki), połączone kreseczkami (właściwie krawędziami). Inżynierowie są bardziej z grafami zapoznani, lecz dla większości jest to zwykle nieczytelny rysunek, jak np. taki:

Jednakże, pomimo swojego niepozornego graficznego przedstawienia, są niezwykle pomocne. Pewnie każdemu z nas, przynajmniej raz zdarzyło się korzystać z nawigacji samochodowej. Podczas wyznaczania najkrótszej trasy pomiędzy miejscem w którym się znajdujemy a docelowym, to właśnie algorytm oparty na teorii grafów wyszukał nam odpowiednią trasę. Więc, co to są te grafy?

Wstęp

Najprościej mówiąc, graf to pewnego rodzaju obiekt. Obiektu posiadającego wierzchołki oraz łączące je linie zwane krawędziami. By być bardziej szczegółowym – mówiąc językiem matematyki – graf to zbiór obiektów (węzłów) połączonych relacjami (krawędziami). A więc każdą relację pomiędzy obiektami możemy zaprezentować graficznie za pomocą grafu. Jeżeli każdej krawędzi grafu przypiszemy pewną wagę¹ która może określać różne parametry (np. wierzchołki są miastami, a krawędzie je łączące symbolizują drogę pomiędzy nimi, to waga oznacza odległość pomiędzy miastami).

Graf skierowany

Graf skierowany składa się z dwóch zbiorów – niepustego zbioru wierzchołków V oraz rodziny A par uporządkowanych elementów zbioru V zwanych krawędziami lub łukami grafu skierowanego. 

G_s = \langle V, A \rangle

gdzie:

A \subset V x V

Graf nieskierowany

Graf skierowany składa się z dwóch zbiorów – niepustego zbioru wierzchołków V oraz rodziny dwuelementowych E uporządkowanych elementów zbioru V zwanych krawędziami. Elementy V oraz E nie muszą być skończone.

G = \langle V, E \rangle

gdzie:

E \subset \lbrace \lbrace x,y \rbrace \subset V \rbrace

Graf ważony

Graf ważony, to graf w którym krawędziom (lub łukom) została przypisana pewna wartość liczbowa / etykieta (waga) służąca do przechowywania dodatkowych informacji o relacjach.

objaśnienie symboli:

V – zbiór wierzchołów N=|V|

E – zbiór krawędzi

A – zbiór łuków (krawędzi skierowanych)

Wykorzystanie grafów

Grafy mogą być wykorzystywane do rozwiązywania szeregów problemów:

• Harmonogramowanie, układanie planów, szeregowanie zadań, kolorowanie map (zagadnienie: kolorowanie grafów),
• Analiza złożonych przedsięwzięć – sieci PERT, GERT,
• Planowanie podróży, wyszukiwanie najkrótszych tras, routing, sieci semantyczne (zagadnienie: problemy dróg ekstremalnych),
• Przepływy w sieciach komputerowych, gazowych, wodociągowych, itp. (zagadnienie: problemy przepływów),
• Przydziały częstotliwości, pracowników do maszyn, kojarzenie małżeństw (zagadnienie: problemy przydziałów),
• Rozpoznawanie wzorców strukturalnych, wyszukiwanie synonimów w BD, wyszukiwanie podobnych stron WWW, ontologie (zagadnienie: podobieństwa grafów).

Omówienie problematyki grafów ich wykorzystania, obliczania grafów, zostaną przestawiane w kolejnych moich publikacjach z cyklu „Teoria Grafów”, tutaj jedynie chciałem zasygnalizować olbrzymie możliwości zastosowania teorii grafów do rozwiązywania trudnych problemów. By zachęcić Was do głębszego poznania, pokaże Wam jedno z możliwych praktycznych zastosowań.

Praktyczne zastosowanie

Chcąc w praktyce zastosować teorię grafów, zademonstruję Wam graf do analizy – a jakże! – jednej z moich głównych dziedzin badań, czyli do analizy ataku phishingowego.

W kolejnych moich wpisach dotyczących phishingu (zaglądaj regularnie!), prezentował będę poszczególne, wykrywalne cechy ataku phishingowego. Uprzedzając – byś dobrze mógł zrozumieć grafy – phishing może być identyfikowalny, poprzez niektóre cechy (np. odpowiednie wartości niektórych pól nagłówka wiadomości email) i cechy te możemy opisać regułami matematycznymi. Utwórzmy więc pewien zbiór cech i reguł które je identyfikują.

Reprezentację ataku phishingowego w postaci grafu (G) możemy przedstawić jako ukierunkowany wykres składający się

• węzłów (V) reprezentujących mierzalne cechy phishingu,
• krawędzi skierowanych (A) łączących poszczególne węzły.

Matematycznie wykres ten możemy zapisać jako: 

G=(V,A)

A w postaci graficznej, graf taki możemy przedstawić jako:

Powyższy przykład można potraktować jako drzewo decyzyjne klasyfikacji binarnej:

If(wykryta została cecha mogąca świadczyć o prawdopodobnym ataku phishingowym) {
     Zaklasyfikuj wiadomość jako phishing 
}

Klasyfikacja binarna, w niektórych przypadkach może okazać się niewystarczająca. Innym podejściem, niż klasyfikacja binarna jest graficzna metoda łączenia krawędziami poszczególnych grup cech phishingowych.  

Konstrukcja grafu

Wykorzystując wyniki działania algorytmu wykrywania i rozpoznawania cech phihsingu w wiadomości email, można określić powiązania pomiędzy wystąpieniami poszczególnych cech. Analizując występowanie cech, w poszczególnych wiadomościach email, można wyznaczyć poszczególne grupy cech, które występują wspólnie lub są poprzez inne cechy (węzły) ze sobą powiązane.

Celem rozpoznania prawidłowości działania algorytmu, dokonano testu jego działania na próbie 50 wiadomości email. Wśród wiadomości znajdowały się te które na podstawie wiedzy eksperckiej znajdował się zbiór wiadomości oznaczonych jako phishingowe, zbiór wiadomości zakwalifikowanych jako spam, oraz zbiór wiadomości będących normalną korespondencją email. Przykładowy wynik działania algorytmu, został przedstawiony w poniższej tablicy (pierwsze 10 rekordów):

Do reprezentacji grafu, (celem uproszczenia modelu) nie będą uwzględnione te cechy (węzły), które w badanym zbiorze, nie wystąpiły (cechy nr: 1, 4, 9, 11, 12, 16).

W analizowanych wiadomościach email, węzłami grafu są wykryte cechy mogące świadczyć o potencjalnym ataku phishingowym – oznaczone zostały wartością 1 (patrz: tabela powyżej), a brak cechy lub wartość nie wskazuje na możliwy phishing oznaczone zostało wartością 0. Krawędziami są połączenia pomiędzy nimi (warunkowane wystąpieniem danego połączenia w danej wiadomości email). Uwzględniając te warunki, można stworzyć graficzne przedstawienie wykrytych cech wskazujących na phishing, co zostało przedstawione na poniższym rysunku:

 Voilà! I powstał nam graf reprezentujący cechy phishingu.

Przedstawiony graf, nie jest grafem pełnym – istnieją wierzchołki w żaden sposób nie połączone ze sobą bezpośrednio krawędziami. Wynika to z faktu, że w analizowanym zbiorze danych, dwie cechy nie wstąpiły w tej samej wiadomości (reprezentowanej jako pojedynczy wiersz).

Jak wspomniałem we wstępie, na grafach można przeprowadzać wiele operacji, których wyniki mogą posłużyć jako rozwiązania konkretnych problemów które są symbolizowane danym grafem. Dla powyższego, skonstruowanego przez nas grafu wyznaczmy łańcuch grafu.

Łańcuch grafu

Łańcuchem grafu możemy nazwać jego marszrutę o różnych gałęziach.

Ocechujmy więc wierzchołki w naszym grafie, zgodnie z przyjętym algorytmem:

1. Oznaczmy dany wierzchołek x cechą „0”,
2. dla wszystkich wierzchołków ocechowanych cechą „c0” cechujemy wszystkie wierzchołki przyległe cechą „c + 1” (c1),
3. jeżeli dany wierzchołek k nie jest ocechowany, to c: = c + 1 i powrót do punktu 2,
4. Jeżeli wierzchołek x^k jest ocechowany, to przejdź do punktu 5.
5. tworzymy łańcuch „od końca” włączając wierzchołki o coraz niższych cechach i dowolne gałęzie je łączące, aż do włączenia x

x^p= 2;     x^k=15

Wyznaczyliśmy więc najkrótszy łańcuch:

<2,d,8,k,10,n,15>

Łańcuch najkrótszy, można wykorzystać, do określenie minimalnej ilości cech, występujących w wiadomościach email, wskazujących na możliwość ataku phishingowego. Problematyka wykorzystania teorii grafów w wykrywaniu ataku phishingowego, będzie przedmiotem moich dalszych badań, które będę systematycznie prezentował na łamach bloga.

Przypisy:

1. Waga – czynnik liczbowy, który jest dołączany do wszystkich obserwacji występujących w funkcji opisującej określony obiekt, w celu zaznaczenia różnego stopnia ważkości (istotności) każdej z tych obserwacji ↩︎