Artykuły

  • Klient systemu Windows 8

    W ramach jednej z prac magisterskich opracowanych na Katedrze Architektury Systemów Komputerowych stworzono klientów projektu COMCUTE dla systemu Windows 8 oraz jego starszych wersji.

    Poniżej zamieszczono link do archiwum z kodem źródłowym klienta działającego pod interfejsem Modern UI w systemie Windows 8. Aplikację można zainstalować bezpośrednio przy użyciu narzędzia Visual Studio 2012 z aktualną licencją dewelopera systemu Windows 8 lub generując pliki binarne i instalując aplikację jako zaufaną (opcja ta jest tylko dostępna w wersji Windows 8 Enterprise).

    COMCUTE_Client_src.zip

    Poniżej zamieszczono archiwum z plikami źródłowymi aplikacji działającej pod Windowsem Vista, 7, 8 (w trybie okienkowym) oraz pliki binarne aplikacji (skompilowane dla architektury 32-bitowej).

    COMCUTE_Client_src.zip

    COMCUTE_Client_W7_bin_x86.zip


  • Efektywne zrównoleglanie obliczeń w systemie klasy grid na przykładzie hipotezy Collatza

    W rozdziale zaprezentowano problem Collatza oraz sposób jego adaptacji, pozwalający na realizację obliczeń w systemie typu grid. Zidentyfikowano również pożądane cechy problemów obliczeniowych, dzięki którym mogą one zostać zrównoleglone w sposób efektywny w systemach typu grid i porównano je z cechami zadań realizowanych typowo przy użyciu klastrów obliczeniowych.

    22.1. Hipoteza Collatza jako problem matematyczny

    Problem Collatza to nierozstrzygnięty problem o wyjątkowo zwięzłym sformułowaniu, jak wiele innych zagadnień teorii liczb. Nazwa pochodzi od nazwiska niemieckiego matematyka Lothara Collatza, który sformułował pewną hipotezę w 1937 roku [4]. Zagadnienie to było również rozpatrywane przez polskiego matematyka Stanisława Ulama (stąd znane jest też jako problem Ulama lub problem 3x+1) [5, 6]. Problem Collatza jest problemem z zakresu teorii liczb i opiera się o ciąg liczbowy zdefiniowany następująco [7]:

    równanie
    (1)

    Analizując powyższą zależność, można wstępnie wywnioskować, że ciąg liczb naturalnych powinien dążyć do nieskończoności, gdyż każda liczba nieparzysta jest zwiększana trzykrotnie, a parzysta zmniejszana jest zaledwie dwukrotnie. Ponadto, każda liczba nieparzysta jest jeszcze zwiększana o 1 po przemnożeniu przez 3.

    Natomiast Collatz postawił hipotezę, że niezależnie od tego, jaką liczbę wybierzemy jako początkową, uzyskamy ostatecznie cykl postaci 4, 2, 1 [1, 18]. Problem pozostaje otwarty do dnia dzisiejszego. Paul Erdős – jeden z matematyków uczestniczących w programie Manhattan – stwierdził, że matematyka nie jest gotowa na tego typu problemy [10]. Kontrast między prostotą sformułowania a złożonością samego problemu jest zaiste intrygujący.

    Hipoteza była weryfikowana w sposób empiryczny dla liczb rzędu nawet 1018 [12,17]. Dotychczas nie odnaleziono liczby początkowej, która nie prowadziłaby do wspomnianego wcześniej cyklu 4, 2, 1. Dlatego w systemie Comcute podjęto się empirycznej weryfikacji powyższej hipotezy dla liczb naturalnych większych niż 1018. Mimo że zrealizowany eksperyment jedynie potwierdził zbieżność do jedynki ciągu liczb Collatza w zakresie do 1030, to jednak umożliwił także sprawdzenie skalowalności obliczeń systemu gridowego.

    22.2. Własności istotne z punktu widzenia zrównoleglenia obliczeń

    Hipoteza Collatza stwierdza, że bez względu na to od jakiej liczby rozpoczniemy obliczenia, w końcu dojdziemy do liczby 1 [13,16]. Weryfikacja, czy dana liczba spełnia hipotezę Collatza, odbywa się na komputerze internauty w sposób niezależny od innych testowanych liczb. Ta właśnie niezależność obliczeń umożliwia efektywne zrównoleglenie w sytuacji, gdy dysponujemy wieloma jednostkami wykonawczymi. W praktyce dochodziło do sytuacji, gdy kilkuset internautów uruchomiło program testujący problem Ulama jednocześnie. Dzięki niezależność obliczeń poszczególne jednostki wykonawcze nie muszą oczekiwać na zakończenie obliczeń na innych węzłach. Nie ma zatem zależności czasowych między operacjami realizowanymi przez różne węzły systemu typu grid.

    Zatem jeśli jeden internauta realizuje obliczenia zaczynając od wartości 97, to ciąg 118 kolejnych liczb przedstawiono poniżej.

    W wypadku zwiększenia wartości początkowej do 1097, potrzebnych jest 137 przekształceń (sekwencję wartości zamieszczono poniżej).

    Jeśli zatem internauta otrzyma paczkę danych do testowania hipotezy Collatza z przedziału od 2 do 10 000, to szacuje się, że niezbędnych jest nie więcej niż 2 mln operacji zmiennoprzecinkowych na sekundę.

    Warto podkreślić, że liczba operacji nie rośnie tak znacząco, jak wartości liczb. Przykładowo 303 operacji wymaga sprawdzenie zbieżności ciągu dla 1018, przy czym sekwencję obliczeń przedstawiono niżej.

    Natomiast zwiększenie wartości do 1036 wymaga 515 operacji wyznaczających następujący ciąg liczb.

    Paradoksalnie testowanie dla 1072 wymaga jedynie 496 operacji wyznaczających zbieżny ciąg liczb. Dla 1084 wymagane są 622 operacje, a dla 10168 wymagane są 880 operacje. Liczba wymaganych operacji rośnie zatem wolniej niż log n, n jest ilością cyfr w liczbie początkowej.

    Kolejną istotną konsekwencją niezależności obliczeń jest brak konieczności synchronizacji stanu pomiędzy różnymi maszynami uczestniczącymi w realizacji zadania. Jest to szczególnie istotne w przypadku systemów typu grid, ponieważ w systemach tych poszczególne węzły mogą znajdować się w odległych geograficznie lokalizacjach. Łącze komunikacyjne pomiędzy takimi węzłami cechuje się relatywnie niskimi prędkościami transmisji danych i dużymi opóźnieniami. Zatem wszelka komunikacja wiąże się z dużym narzutem czasowym. Stoi to w kontraście do klastrów obliczeniowych, gdzie dysponujemy szybkim łączem pomiędzy węzłami, które cechuje się niskimi opóźnieniami. W przypadku sieci Infiniband są to prędkości rzędu gigabitów/sekundę i opóźnienia rzędu mikrosekund. Dla transmisji pomiędzy węzłami obliczeniowymi systemu typu grid oczekiwane prędkości są natomiast na poziomie megabitów/sekundę, a opóźnienia mogą sięgać setek milisekund.

    Kolejną istotną cechą z punktu widzenia obliczeń w systemie typu grid jest stosunek czasu obliczeń do czasu komunikacji. Jak pokazano wcześniej, transmisja danych w systemach typu grid jest kosztowna. W przypadku problemów wymagających przesłania dużej ilości danych i relatywnie prostych obliczeń, przyspieszenie obliczeń dzięki ich zwielokrotnianiu zostanie zniweczone przez narzuty komunikacyjne i przyspieszenie całego systemu będzie znikome w stosunku do systemu działającego sekwencyjnie lub nawet łączny czas wykonania będzie dłuższy niż przy obliczeniach na pojedynczej maszynie. Tego typu problemy możemy efektywnie zrównoleglać na klastrach obliczeniowych. W przypadku badania hipotezy Collatza, danymi wejściowymi dla węzła obliczeniowego jest zakres liczb, który ma zostać przetestowany. Możemy go reprezentować w postaci pary uporządkowanej (początkowa wartość zakresu, ilość kolejnych liczb do przetestowania). Ilość obliczeń do wykonania na danym węźle obliczeniowym, w odniesieniu do rozmiaru danych wejściowy, została przedstawiona w tab. 22.1.

    Tab. 22.1. Oszacowanie ilości obliczeń dla wybranych rozmiarów danych wejściowych

    Dane wejściowe Rozmiar danych wejściowych Ilość obliczeń (liczb do przetestowania)
    1000 1000 9 bajtów 103 liczb
    1000 1000000 12 bajtów 106 liczb
    1000 1000000000 15 bajtów 109 liczb

    Na bazie danych zawartych w tabeli widoczne jest, że liniowy wzrost rozmiaru danych wejściowych wiąże się z wykładniczym zwiększeniem ilości obliczeń. Możemy zatem dowolnie wydłużać czas obliczeń na pojedynczym węźle, nie zwiększając przy tym znacznie ilość danych wejściowych. Należy jednak zauważyć, że wydłużenie czasu przetwarzania pojedynczej paczki danych wejściowych zwiększa ryzyko, iż nie otrzymamy wyniku dla tej paczki z powodu awarii łącza komunikacyjnego bądź odłączenia danego węzła obliczeniowego (np. rezygnacja uczestnika obliczeń w systemie opartym o ideę volunteer computing). Czas obliczeń należy zatem dobrać tak, aby był odpowiednio długi w stosunku do czasu komunikacji, jednak na tyle krótki, aby prawdopodobieństwo otrzymania odpowiedzi było wciąż wysokie. W przypadku systemu BOINC czas jednorazowych obliczeń ustalono na poziomie 15 sekund [3, 14].

    Internauci zaangażowani w program BOINC uczestniczyli w projekcie 3x+1@home którego celem było wyznaczenie kontrprzykładu do hipotezy Collatza. Na stronie WWW zamkniętego już projektu można znaleźć listę liczb-kandydatów, dla których długość ciągu przed osiągnięciem pętli {4,2,1} wyniosła 1000 iteracji [15]. Przykładem takiej liczby, co udało się wyznaczyć za pomocą gridu Comcute, jest wartość zapisana poniżej. Sekwencja liczb składa się ze 1004.

    Kontynuacją zakończonego projektu 3x+1@home jest Collatz Conjecture wykorzystujący infrastrukturę BOINC.

    Kolejnym istotnym aspektem jest rozmiar danych wyjściowych, jakie muszą zostać odesłane po przeprowadzeniu obliczeń. W przypadku problemu Collatza przyjąć można, że dane wyjściowe mają jedną z dwóch postaci:

    • pojedynczy, jednobajtowy znacznik, wskazujący że w zadanym przedziale nie odnaleziono liczby, która zaprzeczałaby hipotezie,
    • liczba, co do której wykryto, że zaprzecza hipotezie.

    Odnalezienie jednej liczby, zaprzeczającej hipotezie Collatza, kończy proces obliczeniowy. Widać zatem, że ilość danych wyjściowych w przypadku omawianego problemu jest niewielka.

    22.3. Optymalizacje sekwencyjnej odmiany problemu i ich ocena w kontekście systemu typu grid

    W przypadku testowania poprawności hipotezy Collatza w środowisku sekwencyjnym, w sposób automatyczny narzucają się dwie możliwe optymalizacje.

    Pierwsza z nich wiąże się ze spostrzeżeniem, że jeśli generując kolejne wartości ciągu (1) dla pewnej liczby początkowej n uzyskamy w pewnym kroku liczbę m, co do której wcześniej wykazaliśmy, że spełnia ona hipotezę, to liczba n również ją spełnia. Wynika to z faktu, że po uzyskaniu liczby m, każdy kolejny wyraz ciągu będzie taki sam, jak dla ciągu, który rozpoczął się od liczby m i osiągnął wartość 1 w jednym ze swoich wyrazów. Bazując na tym spostrzeżeniu możemy skrócić czas testowania poszczególnych liczb i zamiast zawsze dążyć do wartości 1, zatrzymywać obliczenia, gdy trafimy na wcześniej zweryfikowaną już liczbę. Wymaga to jednak utrzymywania informacji o zweryfikowanych wcześniej liczbach. W szczególności, w systemie typu grid, węzły obliczeniowe musiałyby w ramach danych wyjściowych wysyłać wszystkie liczby, które nie zaprzeczają hipotezie. Natomiast w czasie testów kolejnych liczb węzły musiałyby odpytywać centralne repozytorium zawierające zweryfikowane już liczb. Zwiększyłoby to w sposób znaczący ilość komunikacji pomiędzy węzłami tak, że sięgnęłaby ona rzędu ilości obliczeń prowadzonych w systemie. Przy prędkości łącz komunikacyjnych pomiędzy odległymi węzłami systemu typu grid spowodowałoby to drastyczny spadem wydajności.

    Druga możliwa optymalizacja bazuje na spostrzeżeniu, że uzyskanie liczby cn = 1 w ciągu liczb c1, c2, c3 … cn zdefiniowanym zgodnie z formułą (1) oznacza, że nie tylko dowiedliśmy, iż liczba c1 nie przeczy hipotezie Collatza, ale również wszystkie liczby c2, c3… cn-1 nie stanowią jej zaprzeczenia. Wykorzystanie tego spostrzeżenia również wymaga wprowadzenia centralnego repozytorium zweryfikowanych liczb. Ilość danych koniecznych do przesłania w systemie typu grid byłaby tu jeszcze większa nić w poprzednim przypadku. Węzły obliczeniowe, poza liczbami początkowymi, musiałyby przesyłać również wszystkie elementy ciągu na drodze do elementu o wartości 1. Ze wzoru (1) wprost wynika, że ilość takich elementów jest równa przynajmniej logarytmowi o podstawie 2 z liczby początkowej. Zatem również ta modyfikacja nie stanowi optymalizacji dla obliczeń wykonywanych w systemie typu grid.

    22.4. Problem Collatza a twierdzenie Gödla

    Kurt Gödel sformułował w 1930 roku twierdzenie, że jeśli teoria T jest niesprzeczna i zawiera arytmetykę liczb naturalnych, to istnieją zdania A(x) takie, że chociaż wszystkie zdania

    A(0), A(1), A(2), …

    są twierdzeniami teorii T, to jednak zdanie ogólne

    dla każdej liczby naturalnej x zachodzi A(x)

    ani jego zaprzeczenie nie daje się wyprowadzić.

    Przykładem takiego zdania w informatyce jest problem stopu programu komputerowego. Niech dany jest program P. Czy ten program skończy obliczenia w skończonym czasie? Czy zatem istnieje uniwersalny algorytm rozstrzygający o innych algorytmach, czy mają własność stopu?

    W kontekście problemu Collatza widzimy, że problem stopu jest nierozstrzygalny. Oczywiście, gdyby udało się podważyć hipotezę Collatza, to nie byłby to dowód na nieprawdziwość twierdzenia Gödla.

    22.5. Skalowalność obliczeń

    W wyniku przeprowadzonych obliczeń testowano skalowalność systemu za pomocą obliczeń realizowanych na komputerach kilkuset internautów. Po kliknięciu na link projektu Comcute, internauta obserwuje zmieniające się wartości liczb, które podlegają testowaniu zgodnie z hipotezą Collatza (patrz rys. 22.1). Liczby dostarczane są do internauty w paczkach danych charakterystycznych dla systemu Comcute. Po przetestowaniu liczb z paczki danych ograniczonej z góry wartością 1000000000010452200, zwracana jest informacja (wartość 0 – porażka) do serwera S1, który przesyła ją do nadzorującego serwera W1. Serwery W scalają przedziały liczb z informacją o „porażce” i przekazują informację o scalonych przedziałach do serwera Z, który ostatecznie kompletuje zakres zweryfikowanych liczb naturalnych. W wypadku, gdyby została podważona hipoteza Collatza, przewidziano wysyłanie wartości 1.

    Graficzny interfejs obliczeń internauty
    Rys. 22.1. Graficzny interfejs obliczeń internauty

    Warto podkreślić, że kod programu zasadniczo nie zwiększa zajętości pamięci operacyjnej na komputerze internauty, co zaprezentowano na rys. 22.2 w oknie Historia użycia pamięci fizycznej. Natomiast internauta może odczuwać spadek mocy komputera, co obrazuje Historia użycia procesora na rys. 22.2.

    Obciążenie zasobów komputera internauty
    Rys. 22.2. Obciążenie zasobów komputera internauty

    Wartości maksymalne użycia procesora na poziomie 90% osiągane są w okresach, kiedy procesor internauty przetwarza paczkę danych od serwera S. Natomiast, wartości minimalne ok. 10% odpowiadają sytuacjom, gdy odbywała się transmisja paczek danych z serwera. Zatem im szybsza sieć, tym większa wydajność. Ponadto, paczki danych powinny być przesyłane w wielkości uzależnionej od przepustowości połączeń (mogą być mniejsze, przy większej przepustowości), a także od wydajności komputera internauty (im wydajniejszy, tym większe paczki danych).

    W przypadku uzyskania kolejnego połączenia internauty z systemem Comcute i uruchomienia drugiego zadania, użycie procesora nieznacznie rośnie (nawet do 99%), ale także regularnie maleje do wielkości kilku procent (rys. 22.3). Proste prace na komputerze takie jak przygotowywanie dokumentów lub prezentacji, czy serfowanie po Internecie mogą być realizowane w tym wypadku bez zauważenia opóźnień.

    Obciążenie zasobów komputera internauty przy dwóch równoległych obliczeniach gridowych
    Rys. 22.3. Obciążenie zasobów komputera internauty przy dwóch równoległych obliczeniach gridowych
    Obciążenie zasobów komputera internauty przy czterech równoległych obliczeniach gridowych
    Rys. 22.4. Obciążenie zasobów komputera internauty przy czterech równoległych obliczeniach gridowych

    Powyższe dwa połączenia realizowane były za pomocą przeglądarki Internet Explorer w wersji 9. W przypadku uzyskania trzeciego połączenia za pomocą przeglądarki Firefox i uruchomienia trzeciego i czwartego zadania, użycie procesora także nieznacznie rośnie (nawet do 99%), ale także regularnie maleje do wielkości kilku procent (Rys. 22.4). Proste prace na komputerze takie jak przygotowywanie dokumentów lub prezentacji, czy surfowanie po Internecie mogą być w dalszym ciągu realizowane bez zauważenia opóźnień.

    Każde nowe zadanie powoduje niewielki wzrost zajętości pamięci operacyjnej, ale za to wywołanie tego zadania w nowej przeglądarce, to wzrost zajętości o około 120 MB. Na rys. 22.5 przedstawiono obciążenie zasobów internauty przy dziesięciu zadaniach wykonywanych w środowisku trzech przeglądarek IE, Firefox i Safari.

    Obciążenie zasobów komputera internauty przy dziesięciu równoległych obliczeniach gridowych wykonywanych w środowisku trzech przeglądarek
    Rys. 22.5. Obciążenie zasobów komputera internauty przy dziesięciu równoległych obliczeniach gridowych wykonywanych w środowisku trzech przeglądarek

    Przykładem zależności liczby iteracji od wartości początkowej liczb w problemie 3x+1 jest graficzna reprezentacja na rys. 22.6.

    Zależność liczby iteracji od wartości początkowej liczby w problemie Collatza
    Rys. 22.6. Zależność liczby iteracji od wartości początkowej liczby w problemie Collatza [18]

    22.6. Podsumowanie

    Problem testowania hipotezy Collatza posiada cechy, które pozwalają na jego efektywne zrównoleglenie w systemach typu grid. Najistotniejsze z nich to niezależność obliczeń i korzystny stosunek czasu obliczeń na węzłach do czasu komunikacji, który można w łatwy sposób regulować poprzez modyfikację danych wejściowych. Widać dodatkowo, że zmiany, które skracają czas obliczeń w przypadku wykonania sekwencyjnego, mogą niekorzystnie wpływać na wydajność systemu typu grid. Wszelkie optymalizacje należy zawsze oceniać w kontekście docelowego środowiska, w którym będą wykorzystywane.

    22.7. Wykaz literatury

    1. Wirsching Günther J.: The Dynamical System Generated by the 3n+1 Function. Lecture Notes in Mathematics, No. 1681. Springer-Verlag, 1998
    2. Matthews K., The 3x+1 Problem: An Annotated Bibliography, II (2000-2009), Cornell University Library
    3. Vance, Ashlee: Sun and UC Berkeley are about to BOINC. The Register, 2003
    4. Lagarias Jeffrey C.: The 3x + 1 problem: An annotated bibliography, II, arXiv:math.NT/0608208, 2006
    5. Lagarias Jeffrey C: Syracuse problem, in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, 2001
    6. Wirsching Günther J: The Dynamical System Generated by the 3n+1 Function. Number 1681 in Lecture Notes in Mathematics. Springer-Verlag, 1998
    7. Chamberland Marc: A continuous extension of the 3x + 1 problem to the real line. Dynam. Contin. Discrete Impuls Systems 2:4 pp. 495–509, 1996
    8. Letherman Simon, Schleicher Dierk, Wood Reg: The (3n + 1)-Problem and Holomorphic Dynamics. Experimental Mathematics 8:3, pp.241–252, 1999
    9. De Mol, Liesbeth: Tag systems and Collatz-like functions, Theoretical Computer Science, 390:1, 92–101, January 2008
    10. Bruschi, Mario: A generalization of the Collatz problem and conjecture. arXiv:0810.5169 [math.NT], 2008
    11. Andrei Stefan, Masalagiu Cristian: About the Collatz conjecture. Acta Informatica 35 (2): 167. , 1998
    12. Van Bendegem, Jean Paul: The Collatz Conjecture: A Case Study in Mathematical Problem Solving, Logic and Logical Philosophy, Volume 14 (2005), 7–23
    13. Belaga Edward G., Mignotte Maurice: Walking Cautiously into the Collatz Wilderness: Algorithmically, Number Theoretically, Randomly, Fourth Colloquium on Mathematics and Computer Science : Algorithms, Trees, Combinatorics and Probabilities, pp.18–22, Institut Élie Cartan, Nancy, France, September 2006
    14. Belaga Edward G., Mignotte Maurice: Embedding the 3x+1 Conjecture in a 3x+d Context, Experimental Mathematics, Volume 7, issue 2, 1998
    15. Steiner, R.P.: A theorem on the Syracuse problem, Proceedings of the 7th Manitoba Conference on Numerical Mathematics, pp. 553–559, 1977
    16. Simons J., de Weger B.: Theoretical and computational bounds for m-cycles of the 3n + 1 problem, Acta Arithmetica, (online version 1.0, November 18, 2003), 2005
    17. Sinyor J.: The 3x+1 Problem as a String Rewriting System, International Journal of Mathematics and Mathematical Sciences, Volume 2010
    18. Guy Richard K.: Unsolved problems in Number Theory,E17: Permutation Sequences and the Collatz Conjecture, pp.336–337, Springer, 2004

  • Rozproszone łamanie szyfrów

    W rozdziale zaprezentowano podstawowe techniki łamania szyfrów symetrycznych i asymetrycznych o stosunkowo niewielkiej długości kluczy. Przedstawiono ogólną charakterystykę metod łamania szyfrów. Ilustracją tych metod jest zaprezentowana aplikacja służąca do łamania haseł lub badania odporności haseł na odgadnięcie.

    19.1. Wprowadzenie

    We współczesnej kryptografii bezpieczeństwo algorytmu szyfrującego jest oparte na kluczu, a nie na utrzymywaniu algorytmu w tajemnicy (nb. wszystkie takie próby zakończyły się niepowodzeniem). W literaturze opisano sześć klas metod łamania szyfrów. Każda z nich zakłada, że kryptoanalityk posiada pełną wiedzę o stosowanym algorytmie szyfrowania. Kryptoanaliza, czyli działania i prace podejmowane przez kryptoanalityka, pozwala (oczywiście gdy jest zakończona sukcesem) na odtworzenia tekstu jawnego lub klucza na podstawie szyfrogramu. Zajmuje się również wyszukiwaniem słabych punktów systemów kryptograficznych, punktów, które mogłyby otworzyć drogę do poznania tekstu jawnego lub klucza. Działania prowadzące do utraty tajności klucza szyfrującego, wykorzystujące takie inne metody (nie kryptoanalizę, ale np. socjotechnikę), noszą ogólnie miano próby kompromitacji klucza. Łamanie szyfru polega na znalezieniu klucza szyfrującego (deszyfrującego w przypadku asymetrycznym) wiadomość zaszyfrowaną albo znalezieniu tekstu jawnego, który odpowiada danemu szyfrogramowi. Wyróżniamy następujące metody łamania szyfrów [2]:

    1. Łamanie z szyfrogramami – znamy tylko szyfrogram, tryb pracy i długość klucza. Kryptoanalityk posiada jedynie kilka szyfrogramów utworzonych z wykorzystaniem tego samego algorytmu i klucza. Celem jest znalezienie tekstów jawnych odpowiadających innym szyfrogramom utworzonym z wykorzystaniem tego właśnie klucza bądź klucza szyfrującego. Ta metoda nosi także nazwę łamania brutalnego, bowiem polega na badaniu wszystkich możliwych kombinacji bitów klucza aż do znalezienia tej właściwej, dzięki której można dokonać przekształcenia odwrotnego do szyfrowania.

    2. Łamanie ze znanym tekstem jawnym – obok szyfrogramu, trybu pracy i długości klucza znamy także przynajmniej fragment tekstu jawnego, np. początek lub koniec tekstu jawnego. W tej metodzie kryptoanalityk ma w dyspozycji kilka szyfrogramów i odpowiadających im tekstów jawnych. Szyfrogramy są utworzone przy użyciu tego samego klucza tajnego. Celem jest znalezienie tekstów jawnych innych szyfrogramów utworzonych wykorzystaniem tego klucza (np. zapis sesji SSL) bądź tego klucza.

    3. Łamanie z wybranym tekstem jawnym. Ta metoda jest rozwinięciem poprzedniej. Kryptoanalityk otrzymuje sposobność wybrania tekstu jawnego i odpowiadającego mu szyfrogramu. Pozwala to uzyskać więcej informacji o kluczu i dzięki temu można przyśpieszyć łamanie.

    4. Łamanie z adaptacyjnym wyborem tekstu jawnego. Jest to specyficzne rozwinięcie łamania z wybranym tekstem jawnym. Kryptoanalityk wykonuje kolejne próby, wybierając tekst jawny do szyfrowania wg swojego uznania i pewnych wskazówek uzyskanych z wyników poprzednich szyfrowań. Może np. podzielić duży blok tekstu jawnego na mniejsze porcje i przy łamaniu z adaptacyjnie wybranym tekstem jawnym może wybrać kolejny blok tekstu jawnego. W kolejnym kroku wybiera inny blok tekstu jawnego, biorąc pod uwagę skutki pierwszego wyboru i kolejne uzyskane wyniki.

    5. Łamanie z wybranym szyfrogramem. Ta metoda jest stosowane głównie w kryptosystemach z kluczem publicznym. Kryptoanalityk dysponuje zbiorem szyfrogramów i odpowiadających im tekstów jawnych. Może nawet sam je wytworzyć, używając do tego celu dowolnie lub specyficznie (metoda adaptacyjna) wybranych tekstów jawnych i klucza publicznego (który z definicji jest znany). Z tego zbioru wybiera pewne szyfrogramy i podejmuje próby znalezienia klucza szyfrującego (odszyfrowującego), mając do dyspozycji także tekst jawny.

    6. Łamanie z wybranym kluczem. W tej metodzie kryptoanalityk nie zna klucza (nie może go wybrać), ale ma pewną wiedzę o powiązaniach pomiędzy różnymi kluczami stosowanymi w tym samym systemie (np. informacje o generatorach liczb pseudolosowych, technikach używanych do uzyskania tzw. ziarna losowego, itp.)

    Dodatkowo wypada wspomnieć o innej metodzie, wykorzystującej techniki manipulacji socjotechnicznej.

    • Łamanie pod przymusem („z gumową pałką”). Atakujący używa siły fizycznej, przymusu, przekupstwa, gróźb, szantażu, itp., by uzyskać klucz szyfrujący. Jest to metoda skuteczna dużo bardziej niż typowe zabiegi kryptoanalityczne, ale raczej niemożliwa do zastosowania w rozproszonym systemie obliczeniowym.

    Istnieją metody łamania szyfrów symetrycznych (np. DES) zbudowanych wg schematu zwanego siecią Feistela (FN) o złożoności obliczeniowej mniejszej niż łamanie brutalne, np. kryptoanaliza różnicowa [2]. Wymagają one jednak dużych ilości pamięci i z tego powodu są trudne do zastosowania w środowisku rozproszonym ze względu na konieczność w miarę swobodnego dostępu do różnych pośrednich wyników obliczeń.

    Łamania kluczy systemach z kluczem publicznym, oprócz opisanych powyżej metod w p. 5 i 6, mogą wykorzystywać słabości związane z niewłaściwym stosowaniem protokołów z kluczem publicznym, a także technik tworzenia kluczy (zarządzania kluczami). Podawane w literaturze przedmiotu (np. [1,2,4,5]) skuteczne ataki na RSA były możliwe, bowiem użytkownicy nie przestrzegali ograniczeń związanych ze stosowaniem RSA, zestawionych następująco:

    • Znajomość jednej pary wykładników szyfrowania/deszyfrowania dla danego modułu umożliwia atakującemu faktoryzację modułu oraz ewentualnie obliczenie innych par wykładników szyfrowania/deszyfrowania, bez konieczności faktoryzacji n.

    • Wnioskiem z powyższego jest stwierdzenie, że wspólny moduł nie powinien być używany w protokołach wykorzystujących RSA w sieci telekomunikacyjnej.

    • Aby zapobiec atakom skierowanym na małą wartość wykładnika szyfrującego, komunikaty powinny być dopełniane losowymi wartościami w taki sposób, by uzyskać ich długość zbliżoną do modułu n.

    • Wykładniki (e,d) wybierane w protokole powinny być duże.

    Kilka lat temu doniesiono o złamaniu kryptosystemu RSA o znacznej długości klucza (1024 bity), ale okazało się, że projektanci zastosowali w systemie kiepskiej jakości generatory ciągów pseudolosowych stosowanych do budowy elementów kluczy i tym sposobem te klucze złamano. Natomiast rzeczywiście złamano system z modułem 1039 bity (faktoryzacja liczby n=21039-1) [3,4].

    Możliwe są także ataki na protokoły stosujące RSA do szyfrowania i podpisywania, jeśli ich użytkownicy nie przestrzegają określonych zasad:

    • Nie wolno podpisywać ani szyfrować ciągów bitowych nieznanego pochodzenia bądź podstępnie podsuniętych do przetworzenia przez atakującego.

    • Nie wolno używać tej samej pary kluczy (d,e) do różnych celów i w różnych protokołach, np. do szyfrowania i podpisywania równocześnie.

    Obecnie stosowane metody łamania RSA wykorzystują metody tzw. sit liczbowych i rozproszone środowisko obliczeniowe [3,4,5].

    19.2. Rozproszone łamanie szyfrów symetrycznych o stosunkowo niewielkiej długości kluczy

    Łamanie szyfrów symetrycznych w środowisku rozproszonym o stosunkowo niewielkiej długości kluczy, np. DES polega na tym, że usiłujemy znaleźć klucz szyfrujący, by odszyfrować szyfrogram, albo bezpośrednio odtworzyć tekst jawny z szyfrogramu. Operację można scharakteryzować następująco:

    Parametry algorytmu

    Długość bloku – 64 bitów, efektywna długość klucza – 56 bitów (w 64-bitowej sekwencji występuje 8 bitów parzystości).

    Założenia

    Dysponujemy szyfrogramem i odpowiadającym mu fragmentem tekstu jawnego. Ta metoda łamania to wg podanej poprzednio klasyfikacji łamanie brutalne ze znanym tekstem jawnym.

    Zrównoleglenie obliczeń poprzez podział danych

    Polegać to może na tym, że aplikacja internauty otrzymuje blok tekstu jawnego i blok szyfrogramu oraz początkowe bity klucza (np. o liczbie bitów 16-24). Każdy użytkownik otrzymuje inną kombinację początkowych bitów hipotetycznego klucza.

    Zadaniem komputera użytkownika jest zbadanie pozostałych bitów klucza (32-40b) w celu określenia, czy są tą właściwą kombinacją pozwalającą łącznie z początkowymi 16-24 bitami uzyskać z szyfrogramu zadany tekst jawny;

    Zaletą tej metody przetwarzania jest minimalna komunikacja (krótkie ciągi danych, gdy kod algorytmu jest obecny na komputerze internauty), a obliczenia odbywają się niemalże w czasie rzeczywistym (niekiedy kilka sekund). Natomiast czas obliczeń można regulować, ustając długość badanej sekwencji bitów.

    19.3. Rozproszone łamanie haseł typu brute-force (badanie jakości haseł)

    Badanie jakości haseł, jak również ich łamanie bądź odzyskiwanie na drodze znalezienia równoważnego ciągu znaków to jedno z najbardziej popularnych zastosowań kryptografii. Łamanie brutalne haseł o określonej długości, polegające na badaniu wszystkich kombinacji znaków „drukowalnych” danego alfabetu, może być znacząco przyśpieszone poprzez zastosowanie tzw. łamania słownikowego. Nie polega ono na testowaniu wszystkich możliwych kluczy w porządku numerycznym, ale na sprawdzeniu najpierw najłatwiejszych kluczy (ciągów znaków tworzących hipotetyczne hasło). Użytkownicy często wybierają hasła w miarę łatwe do zapamiętania, często zawierające ciągi znaków w jakiś sposób związane z konkretną osobą bądź spośród słów potocznie używanych. Już w latach 60-tych ub. wieku udawało się złamać 30-40% haseł w przeciętnych systemach komputerowych dzięki tej metodzie [2]. Listę tych łatwiejszych haseł tworzy się, kierując następującymi przesłankami:

    • Nazwisko użytkownika, jego inicjały, nazwa konta w systemie i wszelkie kombinacje słów w oparciu o te bazowe, zamieniając duże litery na małe, np. literę o na znak cyfry 0, itp.;

    • Słowa z różnych baz danych zawierających imiona żeńskie i męskie, nazwy biologiczne, geograficzne, popularne medyczne, nazwy bohaterów filmów, książek, komiksów, programów telewizyjnych, słuchowisk radiowych, postaci internetowych, powszechnie używanych wyrażeń i słów wulgarnych, itp., dokonując także podobnych jak powyżej modyfikacji, a także zdrobnień nazw;

    • Różne permutacje słów z podpunktu a i b, z wykorzystaniem zamiany małych liter na duże, cyfr na litery i odwrotnie, itp., uzupełnionych o wszystkie 4-cyfrowe kombinacje liczbowe stosowane w niektórych systemach operacyjnych jako tzw. wydłużenie hasła (tzw. salting) przeciwdziałające ułatwieniom w jego złamaniu;

    • Listę popularnych słów obcojęzycznych, używanych w różnych środowiskach kulturowych i zawodowych, określenia żargonowe, oraz ich odpowiedniki sylabowe w danym języku – poddane takim samym permutacjom jak w podpunkcie c;

    • Kombinacje słów – pary, trójki słów z podpunktów a-d.

    Tak przygotowana lista potencjalnych haseł może być wcześniej wygenerowana w trybie offline, przekształcona z wykorzystaniem wskazanych jednokierunkowych funkcji skrótu (np. DES-CBC, MD5, SHA-1, RIPEMD) i zapisana do pliku. Przed rozpoczęciem jakiegokolwiek łamania brutalnego najpierw należy sprawdzić tak wygenerowaną listę skrótów w celu zbadania, czy nie występuje zgodność z danym skrótem hasła.

    Ułatwieniem w łamaniu haseł mogą być słabości stosowanych funkcji skrótu. Już w połowie lat 90-tych ub. wieku opublikowano doniesienia o stosunkowo łatwych możliwościach wystąpienia kolizji dla jednokierunkowych funkcji skrótu MD-4 i MD-5 [7]. Kolizją oznaczamy sytuację, w której znajdujemy ciąg znaków skracający się do tej samej wartości skrótu. W przypadku funkcji MD-4 i MD-5 jest to znacznie łatwiejsze niż łamanie brutalne. Od tego czasu nie zaleca się stosowania tych funkcji skrótu w poważnych zastosowaniach kryptografii, ale nadal wielu producentów, np. systemów operacyjnych używa funkcji MD-5 do tworzenia skrótów haseł użytkowników przechowywanych w plikach systemowych. Od części tych słabości nie jest wolna także stosowana, m.in. w Polsce do tworzenia tzw. kwalifikowanych podpisów elektronicznych, funkcja skrótu SHA-1 [6]. Z tego też względu opracowano i zaczęto stosować dłuższe (256 do 512 bitów) funkcje skrótu tworzące standard SHA-2. Obecnie trwają prace nad standardem SHA-3.

    W dalszej części punktu przedstawiono charakterystykę obliczeń dla rozproszonego łamania brutalnego haseł, wykorzystujących zgłoszone do współpracy komputery (część ich zdolności obliczeniowych):

    Rozproszony system obliczeń

    System obliczeń składa się z grupy węzłów wewnętrznych (przyjmujących zlecenia wykonania obliczeń, dzielących dane zadania na paczki, organizujące obliczenia we współpracy z zewnętrznymi węzłami), węzłów zewnętrznych (przekazujących na żądanie kody aplikacji i kolejne paczki danych do współpracujących komputerów internautów) i komputerów wykonujących obliczenia (zgłoszonych dobrowolnie użytkowników biorących udział w całym przedsięwzięciu);

    Parametry obliczeń

    Długość wartości skrótu – 128b (MD5), 160b (SHA-1, RIPEMD), 256b (SHA-256), długość ciągu znaków hasła – od 1 do pewnej górnej granicy.

    Założenia

    Dysponujemy wartością skrótu hasła i typem stosowanej funkcji skrótu, pomocna może być informacja o użytkowniku (rozbudowa o elementy tzw. łamania słownikowego). Ten sposób znajdowania haseł jest podobny do podanej poprzednio klasyfikacji metody łamania z szyfrogramem.

    Zrównoleglenie obliczeń poprzez podział danych

    Aplikacja uruchomiona na komputerze użytkownika (współpracującego z rozproszonym systemem obliczeń) otrzymuje wartość skrótu, kod funkcji do obliczeń skrótu i początkowy ciąg znaków hasła. Każdy komputer użytkownika otrzymuje inną kombinację początkowych znaków hipotetycznego hasła (patrz rys. 19.1).

    Ilustracja sekwencji działań podczas rozproszonego łamania haseł
    Rys. 19.1. Ilustracja sekwencji działań podczas rozproszonego łamania haseł

    Zadaniem aplikacji na komputerze użytkownika jest zbadanie pozostałych hipotetycznych ciągów znaków hasła (uzupełnienie zadanego ciągu początkowego) o długości od 1 znaku do 3 znaków większej od zadanej w celu ustalenia, czy są one łącznie tą właściwą kombinacją pozwalającą wyliczyć zadaną wartość funkcji skrótu.

    Zalety

    Minimalna komunikacja, a obliczenia niemalże w czasie rzeczywistym (niekiedy kilka sekund); czas obliczeń można regulować, ustając długość badanej sekwencji znaków.

    19.4. Przykład aplikacji

    W dalszej części tego podpunktu przedstawiono przykład aplikacji rozproszonego łamania haseł zrealizowanej poza środowiskiem Comcute, ale przygotowanej z myślą o przyszłej implementacji w systemie laboratoryjnym Comcute Politechniki Gdańskiej. Przewidziano, że będą łamane hasła przechowywane w postaci skrótów utworzonych z wykorzystaniem jednokierunkowych funkcji MD5 oraz SHA-1. Aplikacja została stworzona z wykorzystaniem języków Python, C++ i JavaScript.

    Architektura aplikacji obejmuje następujące elementy:

    • Serwer sterujący – główny element, zwany również kontrolerem. Jest to wielowątkowy serwer TCP/IP, który zajmuje się dzieleniem przestrzeni problemu na mniejsze zakresy, przydziałem zadań oraz przyjmowaniem rozwiązań, a także ich weryfikacją. Ta część de facto symuluje zachowanie warstw W i Z środowiska COMCUTE.
    • Baza danych MySQL, w której przechowywane są informacje o użytkownikach systemu, wygenerowanych zadaniach, a także problemach, które należy jeszcze zaadresować. Jest to symulacja warstwy danych serwerów W środowiska Comcute.
    • Moduł serwera WWW. Jest to symulacja serwerów S środowiska Comcute.
    • Klienci:
      • pierwszego typu – łączą się poprzez aplikację desktopową bezpośrednio z kontrolerem, będąc świadomymi uczestnikami obliczeń (voluntary computing);
      • drugiego rodzaju, nie są świadom faktu brania udziału w projekcie, stąd nie mogą oni w sposób bezpośredni komunikować się z kontrolerem.
    • Serwer sterujący – Jest to aplikacja napisana w języku Python, zadaniem której, jest podział przestrzeni problemu na zakresy obliczeń stanowiące części zadań serwowanych klientom. Oprócz tego odpowiedzialny jest on też za przyjmowanie i weryfikację wyników zgłoszonych przez klientów.

    Komunikacja z kontrolerem przebiega przy użyciu gniazd TCP/IP, z wykorzystaniem protokołu tekstowego przypominającego np. protokół FTP. W komunikacji udział biorą obiekty zadań, opakowane w formie dokumentów formatu XML. Przykładowe zadanie w formacie XML ma więc postać (dla klientów pierwszego typu):

    <?xml version="1.0" encoding="UTF-8" ?>
    <task id="17">
          <problem>
          <algorithm>md5</algorithm>
          <dictionary>ABCDEFGHIJKLMNOPQRSTUVWXYZ</dictionary>
                 <range_start>AAAAA</range_start>
                 <range_end>EEEAA</range_end>
                 <expected_length>5</expected_length>
                 <hash>9da4fc50e09e5eeb8ae8149ef4f23792</hash>
          </problem>
          <challenge>a challenging string</challenge>
    </task>
    

    Odpowiedź zgłaszana jest natomiast w następujący sposób:

    <?xml version="1.0"?>
    <task id="17">
          <result found="T">CCCCC</result>
          <challenge>a challenging string</challenge>
    </task>
    

    Co oznacza że zostało znalezione rozwiązane. W tym momencie można dokonać sprawdzenia, czy rzeczywiście znaleziono kolizję (hasło). W tym celu na serwerze (kontrolerze) należy wykonać obliczenia sprawdzające, czy znaleziony łańcuch znaków skraca się do zadanej wartości przy wykorzystaniu wskazanej jednokierunkowej funkcji skrótu.

    Wprowadzony został moduł serwera WWW (WebServer), będącego swoistym rodzajem proxy, jako pośrednik pomiędzy kontrolerem a klientami (drugiego typu). W tym przypadku mamy do czynienia z wieloma użytkownikami, którzy nie są zbyt świadomi faktu użyczania swej mocy obliczeniowej. Z uwagi na pewną trudność związaną z obsługą protokołu zgłaszania odpowiedzi, zaproponowany został element pośredniczący pomiędzy klientem niejawnym, a kontrolerem.

    Kod aplikacji serwera został on napisany w języku Python i zapewnia podstawową oczekiwaną funkcjonalność, tj. jest w stanie udostępniać pewne zasoby internetowe (strony www, grafikę czy też aplety), jak również obsługiwać żądania rodziny GET/POST i inne, jak np. możliwość dynamicznego wypełniania szablonów dokumentów, informacjami charakterystycznymi dla zadań naszego systemu. Serwer jest pośrednikiem i z punktu widzenia kontrolera jest użytkownikiem reprezentującym wszystkich klientów drugiego typu. W momencie nawiązywania połączenia, przedstawia się więc on jako inna maszyna, następnie pobiera w jej imieniu zadanie. Zadanie to przesyła, używając jednego z dostępnych silników, dla klienta – zwykle przeglądarki internetowej – po czym odbiera od klienta wynik, który znowu raportuje do kontrolera, również w imieniu klienta. Uzupełnienie działania serwera stanowią proste moduły, zwane też silnikami, które realizują właściwą funkcjonalność obliczeniową. Przygotowane zostały 3 takie implementacje:

    • Silnik JavaScript pozwala wstawić skrypt na dowolną stronę, który raz uruchomiony, zajmuje się wykonaniem obliczeń, a następnie odesłaniem rezultatu do serwera, z którego został pobrany. Realizuje to przy wykorzystaniu technologii AJAX. Skrypt ma możliwość wprowadzenia opóźnień czasowych, dzięki którym pozostaje niezauważalny, gdyż zabiera relatywnie mało zasobów systemowych.
    • Silnik Flash został zrealizowany tylko w częściowej funkcjonalności. Nie występuje tu osadzenie obiektu (WDF) na stronie, są dostępne jedynie moduły w postaci plików typu .FLA i .AS, z którymi to współpracuje zmodyfikowana wersja WebServera.
    • Silnik apletów Java uruchamia aplety Javy poprzez mechanizm JNLP. Poprzez skrypt, który je ładuje, są wstawiane parametry do obliczeń. Aby można było odesłać wyniki obliczeń nie podpisując apletu, odsyła się je na WebServer za pomocą java.net.URLConnection.

    Klient drugiego typu na żądanie (GET/POST) ze strony serwera otrzymuje skrypt (JavaScript, aplet Java, Flash), zawierający funkcję skrótu (MD5, SHA1) i zakres danych do obliczeń. Przewidziano możliwość wykonania obliczeń na kartach graficznych z rodziny AMD (dawne ATI).

    Po otrzymaniu wyniku obliczeń od klienta serwer przekazuje go do kontrolera.

    Zastosowane technologie: MPI, Python, C++, JavaScript.

    19.5. Rozproszone łamanie szyfrów asymetrycznych o stosunkowo niewielkiej długości kluczy, np. RSA z modułem 512b

    Aktualne doniesienia [3,4] na temat łamania kluczy RSA wskazują, że dokonano rozproszonego łamania RSA z kluczem (a faktycznie modułem n=786 bitów – ok. 193 cyfr dziesiętnych), zakończone 12 grudnia 2009 roku. Operacja przebiegała w czasie 2,5 roku z wykorzystaniem pracy setek komputerów. Oceny dokonywane przez różnych kryptoanalityków mówią, że złamanie klucza o długości 1024 bitów stanie się możliwe na przestrzeni najbliższych kilkunastu lat.

    Charakterystykę rozproszonego łamania RSA opisano następująco:

    Parametry

    Tekst jawny o długości bloku – np. 128 b, klucz publiczny – (n, e).

    Założenia

    Dysponujemy szyfrogramem (np. podpisem) S i tekstem jawnym (skrót podpisywanej wiadomości) H oraz pewną początkową liczbą bitów klucza prywatnego albo zakresem badanych liczb pierwszych;

    Zrównoleglenie obliczeń poprzez podział danych

    Aplikacja internauty otrzymuje aplikację do badania liczb pierwszych, tekst jawny, szyfrogram oraz klucz publiczny. Każdy użytkownik otrzymuje inną kombinację początkowych bitów hipotetycznego klucza prywatnego albo inny hipotetyczny przedział dla liczby poszukiwanej pierwszej, np. p. Zadaniem internauty jest znalezienie takiej pary liczb pierwszych p,q (problem faktoryzacji), że n=pq oraz liczby d będącej tożsamościową odwrotnością e, tzn. Sd mod n = H, Hed mod n ≡ H; Do badania, czy dana liczba x jest liczbą pierwszą, można użyć:

    • Testu Fermata – dla liczby x i znanej liczby pierwszej a obliczamy f ≡ a x‑1 (mod x); jeśli f ≠1(mod x), to x nie jest liczbą pierwszą, a w przeciwnym wypadku prawdopodobnie; test powtarzamy dla upewnienia się dla kilku liczb pierwszych a, np. 2, 5, 7, 11,13. Niestety, istnieją liczby złożone (liczby Carmichaela), dla których zachodzi a x-1 (mod x) ≡ 1(mod x), dla dowolnego a względnie pierwszego z x. Zaletą tego jest testu jest prostota obliczeń.
    • Testu Millera-Rabina – który jest bardziej skomplikowany. Wykonujemy go następująco:
      • Dla danego nieparzystego n niech an−1 = t2s, gdzie t jest nieparzyste.
        1. Jeśli liczba n jest liczbą pierwszą, to an−1 ≡1 (mod n) (zachodzi małe twierdzenie Fermata).
        2. Jeśli liczba n jest liczbą pierwszą i równanie dla 0 < r ≤ s, to
        3. równanie albo równanie
        4. Losujemy 0 < a < n i obliczamy: at mod n, a2tmod n, a4t mod n, . . . , , an−1mod n.
        5. Jeśli ostatnia liczba z powyższej listy jest różna od 1 lub, przeglądając je od końca, pierwsza napotkana liczba różna od 1 jest tez różna od n−1, to ajest świadkiem, że n jest złożona.
        6. Dla każdej liczby złożonej n prawdopodobieństwo tego, że losowo wybrane ajest świadkiem, wynosi co najmniej 3/4.
        7. eśli wypróbujemy m losowo wybranych wartości a i żadna z nich nie okaże się świadkiem złożoności dla n, to z prawdopodobieństwem co najmniej 1 − (1/4)m liczba n jest pierwsza. Im więcej badań przeprowadzimy, tym większe szanse na to, że liczba n jest liczbą pierwszą.
    • Testu pierwszości Solovaya–Strassena, który korzysta z obliczeń symbolu Legendre’a i symbolu Jacobiego, przez co obliczenia są jeszcze bardziej skomplikowane. Pewność znalezienia liczby pierwszej opiera na podobnych statystycznych badaniach jak w przypadku testu Millera-Rabina.

    Do faktoryzacji liczby n można użyć wielu algorytmów. Aktualnie najlepszym algorytmem do rozwiązania tego problemu jest ogólne sito ciał liczbowych (GNFS) [1,3], o podwykładniczej złożoności exp((c+O(1))n1/3 log2/3 n) dla c<2.

    Popularną metodą jest także użycie kwadratowego sita liczbowego. Korzystamy tutaj z prostej własności: jeśli n = a2 − b2, to n = (a + b)(a − b). Poszukiwanie czynników liczby n polega na testowaniu kolejnych wartości a począwszy od najbliższej mniejszej od sqrt(n) i sprawdzenia, czy liczba a2 –n jest kwadratem. Jeśli tak, to znaleźliśmy takie b2= a2 –n, a zatem rozkład liczby n.

    Do faktoryzacji liczby n można także użyć np. metody Pollarda. Każdy internauta otrzymuje zakres liczb x i y do zbadania, czy różnica (x – y) jest równa 0 mod n. Jeśli tak, to NWD(x – y, n), czyli znaleziono dzielnik liczby n. Do generowania liczb można użyć generatora Brenta – który wykorzystuje wzór x2 – c, c≠2 – i dla kolejnych iterowań dokonujemy sprawdzenia, czy zachodzi poszukiwana zależność.

    Niezbędna jest jednak dodatkowa uwaga. Zanim przystąpimy do wyczerpującego ataku (np. faktoryzacja GNFS), należy wykonać różnego rodzaju badania i testy wykorzystujące słabości implementacji RSA. Należą do nich:

    • Ataki elementarne, wykorzystujące fakt stosowania wspólnego modułu dla grupy par kluczy oraz tzw. „oślepiania”, czyli skłonienia właściciela klucza prywatnego do podpisania specjalnie spreparowanej wiadomości, wyglądającej jak losowy ciąg bitów [1,2];
    • Łamanie wg metody Wienera, opartej o mały wykładnik prywatny d. Użycie tej metody może złamać klucz prywatny w czasie liniowym na drodze kolejnych przybliżeń;
    • Niekiedy w celu redukcji czasu weryfikacji podpisu elektronicznego jest wybierany niski wykładnik e (klucz publiczny), co też może być przedmiotem ataku [1,2]. Najpopularniejszy atak na niski wykładnik publiczny RSA jest oparty na twierdzeniu Coppersmitha. Wśród popularnych implementacji [5] opartych na tym twierdzeniu znajdujemy algorytm LLL (Lovasz, Lenstra, Lenstra jr.), atak Hastada, atak Franklina-Reitera, atak częściową ekspozycją klucza.
    • Ataki na implementację RSA – skierowane na błędy techniczne popełnione przez informatyków wdrażających schemat. Wśród tych ataków wyróżniamy: ataki czasowe – opierają się na pomiarze czasu realizacji operacji kryptograficznych w kartach chipowych, ataki eksploatujące metody przyspieszania realizacji podpisu RSA, ataki na losowe uzupełnienie szyfrowanej wiadomości, ataki wykorzystujące wahania poboru energii podczas realizacji działań kryptograficznych (karty chipowe), a także ataki skierowane na wykrycie słabości zastosowanych generatorów liczb pseudolosowych.

    Zalety: czas obliczeń można regulować, ustając długość zadanej sekwencji bitów lub wielkość przedziału badanych liczb pierwszych.

    19.6. Podsumowanie

    W rozdziale przedstawiono metody rozproszonego łamania szyfrów symetrycznych, łamania haseł bądź testowania ich odporności na odgadnięcie oraz wybrane metody łamania schematów asymetrycznych na przykładzie algorytmu RSA. Zaprezentowano także przykład aplikacji służącej do rozproszonego łamania haseł z wykorzystaniem mocy obliczeniowej komputerów wolontariuszy uczestniczących w obliczeniach. Z przedstawionych rozważań wynika, że wybrane obliczenia kryptograficzne realizowane w środowisku rozproszonym mają duże znaczenie praktyczne i pozwalają znacznie przyśpieszyć różnego rodzaju działania mające znaczenie dla bezpieczeństwa różnych firm, organizacji i instytucji.

    19.7. Wykaz literatury

    1. A. J. Menezes, P. C. van Oorschot, S. A. Vanstone: Handbook of Applied Cryptography (Kryptografia stosowana), WNT 2005.
    2. B. Schneier: Kryptografia dla praktyków, wyd.2, WNT 2000.
    3. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé, J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A. Osvik, H. te Riele, A. Timofeev, P. Zimmermann: Factorization of a 768-bit RSA modulus, version 1.4, February 18, 2010, http://eprint.iacr.org/2010/006.pdf
    4. http://pl.wikipedia.org/wiki/RSA_Factoring_Challenge
    5. http://e-wiki.pl/articles/30RSA.php
    6. Cryptanalysis of SHA-1, Schneier on Security, http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html
    7. Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger: MD5 considered harmful today, http://www.win.tue.nl/hashclash/rogue-ca/

  • Bezpieczeństwo w monitoringu

    Zaproponowano szereg algorytmów realizujących aspekty bezpieczeństwa zorientowane na aplikacje monitorujące. W znaczącej części pozwolą one na zastąpienie pracy czynnika ludzkiego przy przeglądaniu lub analizie zapisów video z monitorowanych miejsc lub obszarów. Ze względu na szeroki potencjalny obszar, zakres zastosowań praktycznych oraz potencjalne efekty natury ekonomicznej u potencjalnych klientów spodziewane jest szerokie wykorzystanie tego typu rozwiązań w automatycznym monitoringu zarówno typu offline jak i online.

    15.1. Problemy realizacyjne w aktywnym monitoringu video

    W systemowych rozwiązaniach informatycznych w zakresie aktywnego monitoringu podstawowym problemem realizacyjnym jest analiza obrazów wideo w celu wykrycia sytuacji potencjalnie niebezpiecznych lub nietypowych. W automatycznych systemach nadzoru należy sklasyfikować sytuacje, efekty, obiekty, zdarzenia, etc. będące przedmiotem potencjalnego zainteresowania, a następnie zastosować odpowiednie algorytmy poszukujące ich w strumieniach (online) lub zapisach (offline) video.

    15.1.1. Wykrywanie niebezpiecznych przedmiotów lub obiektów w obrazie

    W przypadku obserwacji lub też rejestracji transmisji monitoringu z kamer to człowiek podejmuje decyzje dotyczące ewentualnej zakwalifikowania obserwowanego obrazu do sytuacji interesujących. Stąd też w tego typu zastosowaniach konieczna jest aktywna obserwacja obrazów z kamer przez służby nadzoru. W wypadku zastosowania systemu Comcute istnieje możliwość automatycznego wykrywania potencjalnie niebezpiecznych (niepożądanych) przedmiotów bądź obiektów pojawiających się w obserwowanym obszarze. Rejestracja wideo może być podzielona na klatki, każda klatka może zostać wysłana do przetwarzania u określonego internauty. Proponuje się opracowanie bazy wzorców niepożądanych obiektów lub przedmiotów oraz ich wykrywanie. Dla przykładu przedmiotami potencjalnie niebezpiecznymi mogą być: duże torby lub walizki (z potencjalnie niebezpieczną zawartością), noże, czy broń palna. Szersze zastosowania mogą dotyczyć np. wykrywania ciężarówek (tirów) na drogach lub miejscach, gdzie nie powinny się one poruszać lub pojawiać, albo też samochodów na drogach z zakazem ruchu. Zadaniem aplikacji jest wykrycie na obrazie interesującego obiektu z bazy wzorców oraz wysłanie odpowiedniego sygnału dla służb, aby zdecydowały o ostatecznej klasyfikacji danego analizowanego przypadku.

    15.1.2. Wykrywanie anomalii natury ogólnej w obrazie z kamer

    W praktyce monitorowania zwykle poszczególne klatki z zapisu monitoringu statystycznie niewiele się od siebie różnią. Większość planu obrazu zajmuje tło, natomiast obiekty, które pojawiają się w zakresie wizyjnym, zajmują stosunkowo niewielki procent powierzchni. Celem aplikacji jest wykrywanie sytuacji, gdy zmiany obserwowanego tła są ponadprzeciętne. Dla statycznego obrazu można po wstępnym odfiltrowaniu wyznaczyć określony wzorzec tła (policzyć np. sygnaturę lub model widmowy). Wzorzec ten po korelacji z obrazem aktualnym (przetworzonym) pokazuje skalę potencjalnych zmian. Jeżeli zmiany te są zbyt duże, to zgłaszany jest sygnał do obsługi. Jako przykład zastosowania można podać wykrycie sytuacji zasnucia obrazu parkingu, lotniska czy drogi np.: gęstą mgłą, ale również pojawienie się np. dymu zasłaniającego znaczną część widoku kamery, czy zasłonięcie obiektywu kamery np. ręką lub innym przedmiotem. W przypadku trywialnym będzie to szybkie wykrycie odłączenia kamery (transmisja czarnego tła). W przypadku monitorowania przestrzeni, gdzie praktycznie nic nie powinno się pojawiać (ochrona obiektów), na podstawie różnic w obrazach można otrzymać sygnał o pojawieniu się nietypowych zmian (bez klasyfikacji co to jest).

    15.1.3. Wykrywanie dynamicznych zmian w obrazach monitorujących

    W przypadku dużych i dynamicznych zmian pomiędzy klatkami, zmiany te świadczyć mogą o potencjalnie interesujących sytuacjach. Przy wykorzystaniu operacji korelacji (porównania ze sobą) sekwencji kolejnych klatek i zaobserwowaniu różnic można wykryć potencjalnie interesujące sytuacje, takie jak: szybkie rozprzestrzenianie się dymu we fragmencie obrazu, wybuch obiektu w tle, rozszerzający się pożar, zbyt szybko poruszający się obiekt (np. samochód czy motocykl). W aplikacji wymagane jest wykonanie szeregu testów i prób, aby dla określonej kamery (tło, środowisko, dynamizm zmian) określić wartości progowe dla zgłaszania sygnału o wykryciu potencjalnych odstępstw od normy. Aplikacja może działać zarówno online (sygnały pojawiają się w czasie rzeczywistym zaistnienia zdarzeń), jak i offline (czyli sprawdzania archiwalnych zapisów w celu dotarcia do interesujących fragmentów zapisu z monitoringu).

    15.2. Algorytmy przetwarzania sekwencji wideo

    Poniżej przedstawiono ogólną koncepcję realizacyjną dla algorytmów przetwarzania sekwencji obrazów video. Zaprezentowano problematykę przechowywania oraz przetwarzania obrazów. Omówiono konwolucję dwu– i trójwymiarową jako typową technikę dla przetwarzania obrazów. Pokazano jej praktyczne zastosowanie przy wykrywaniu cech charakterystycznych dla obiektów. Zwrócono uwagę na szerokie możliwości zrównoleglenia algorytmów tego typu w praktyce oraz ich wykonywania w rozproszonym środowisku rozległej sieci komputerowej [1].

    Nowoczesne algorytmy i techniki przetwarzania obrazów pozwalają na wszechstronną analizę oraz obróbkę obrazów nie tylko w zakresie typowych operacji, takich jak: skalowanie, zmiana kontrastu, filtracja w zakresie nasycenia, poprawa jakości i kolorystyki, etc., ale także w zakresie analizy i rozpoznawania obiektów oraz cech obiektów prezentowanych na obrazach. Wśród zastosowań można tutaj wymienić: lokalizację oraz śledzenie trajektorii obiektów ruchomych, nawigację dla ruchomych obiektów naziemnych i latających, robotykę przemysłową czy techniki radarowe oraz sonarowe. Istnieją generalnie dwa podejścia realizacyjne: w pierwszym projektuje się wyspecjalizowane układy scalone przeznaczone dla określonych algorytmów, w drugim stosuje się systemy oparte o zrównoleglanie obliczeń, a następnie scalanie ich wyników. Podejście drugie zapewnia większą elastyczność oraz znacznie większą przydatność dla prac naukowo-badawczych w zakresie testowania i weryfikacji nowych technik i algorytmów, a w szczególności pozwala na rozpraszanie obliczeń w sieciach rozległych. Pożądanym aplikacyjnie jest przetwarzanie w czasie rzeczywistym, gdzie przetwarzanie sekwencji obrazów wymaga, aby odpowiedź systemu komputerowego pojawiała się nie później niż nadejście kolejnej klatki z urządzenia rejestrującego [2].

    15.2.1. Techniki przetwarzania obrazów – konwolucja

    Pojedynczy obraz cyfrowy reprezentowany jest zazwyczaj w postaci matrycy punktów w zadanej rozdzielczości. Każdy z punktów opisany jest poprzez informację o kolorze – w przypadku obrazów barwnych, lub stopniu szarości – w przypadku obrazów monochromatycznych. Dla reprezentacji obrazów barwnych stosuję się często reprezentację typu RGB, która wymaga przechowywania informacji oddzielnie o trzech barwach składowych. Inną reprezentacją jest tzw. pseudo-kolor, wówczas odpowiednie barwy są ponumerowane i identyfikacja z fizycznym kolorem odbywa się poprzez odwołania do tablicy wzorcowej (palety). Dla celów przetwarzania obrazów często stosuje się obrazy reprezentowane w skali szarości ze względu zarówno na jednowartościowy opis punktu na obrazie, jak i bezpośrednie powiązanie tej wartości z graficzną reprezentacją wyrażoną odcieniem szarości. W zakresie formatów dla zapisu ciągłego (np. fragment filmu) stosuje się (odpowiednio spakowaną) sekwencję klatek składowych.

    Jedną z typowych technik przetwarzania (ogólnie pojętych) sygnałów jest konwolucja (ang. convolution) [3]. Konwolucja n-wymiarowa powstaje poprzez uogólnienie konwolucji (n-1)-wymiarowej w n-ty wymiar. Idea konwolucji jednowymiarowej przedstawiona została w formule (1), gdzie I reprezentuje wektor numerycznych danych wejściowych, K to jednowymiarowy kernel, a O to wektor danych wyjściowych. Jak widać wektor danych wyjściowych O w (1) powstaje poprzez wymnożenie i zsumowanie kolejnych wartości sygnału z odpowiednimi wartościami kernela K.

    równanie
    (1)

    Poprzez matematyczną generalizację konwolucji jednowymiarowej w kolejny wymiar otrzymujemy konwolucję dwuwymiarową (2), która może już być wykorzystywana dla przetwarzania pojedynczych klatek czy obrazów.

    równanie
    (2)

    Po przekształceniach oraz przeskalowaniu indeksów otrzymujemy formuły (3) i (4), które mogą być zastosowane bezpośrednio w praktyce. Formuła (3) opisuje proces obliczania wartości dla piksela o współrzędnych O[x, y]. Formuła (4) opisuje cały obraz wyjściowy O. W praktyce, obraz wejściowy I jest reprezentowany poprzez matrycę N1xN2 (np. o wymiarach rzędu 800×600) w odcieniach szarości o wartościach 0-255. Rozmiar kernela K w typowych zastosowaniach nie przekracza wielkości kilkunastu dla r1 i r2. Jak pokazuje formuła (4) rozmiar obrazu wyjściowego O wynosi N1–r1+1 na N2–r2+1.

    równanie
    (3)
    równanie
    (4)

    Konwolucja dwuwymiarowa posiada swoją interpretację graficzną, która przedstawiona została na rys. 15.1.

    Geometryczna interpretacja konwolucji dwuwymiarowej
    Rys. 15.1. Geometryczna interpretacja konwolucji dwuwymiarowej

    Jak widać w formułach (3) i (4), na wynikową wartość dla piksela O[x, y] mają wpływ wartości pikseli sąsiednich oraz wartości zawarte w kernelu K. Przy odpowiednim doborze rozmiarów r1, r2 oraz wartości dla kernela K wśród możliwych do realizacji technik przetwarzania wymienić można między innymi: poprawę kontrastu, wyostrzenie lub rozmycie obrazu, detekcje krawędzi oraz wszelkiego rodzaju filtracje.

    Z formuł (3) i (4) wynika, że konwolucja dla obrazu I to ciąg powtarzających się jednakowych i niezależnych od siebie operacji mnożenia i dodawania. Algorytmy wykorzystujące konwolucję nadają się do zrównoleglenia i rozproszenia obliczeń ze względu na względną niezależność poszczególnych operacji składowych. W rozwiązaniach równoległych zwykle wykonuje się rozproszenie pętli programowych zgodne z formułami (3) i (4), z rozbiciem obrazu I na podfragmenty i obliczaniem składowych konwolucji osobno dla każdego podfragmentu na niezależnej podjednostce.

    Konwolucja dwuwymiarowa dotyczy operacji na pojedynczych klatkach lub obrazach. Poprzez uogólnienie konwolucji dwuwymiarowej w dziedzinę czasową otrzymujemy trójwymiarową konwolucję przestrzenno-czasową. Geometryczna interpretacja tej konwolucji dla czasowego rozmiaru sekwencji wynoszącego 5 przedstawiona została na rys. 15.2. Przy wykorzystaniu konwolucji czasowo-przestrzennej można uzyskać różnego rodzaju filtracje polegające np. na eliminacji określonych obiektów z filmu video, generację kolejnej klatki na podstawie klatek poprzednich, etc. Dla tego typu algorytmów możliwości zrównoleglenia operują w trzech stopniach swobody. Podobnie jak dla konwolucji dwuwymiarowej, dwa pierwsze stopnie swobody dotyczą rozmiarów pojedynczej klatki N1xN2. Do tego dochodzi stopień swobody związany z długością sekwencji klatek [4].

    Interpretacja geometryczna konwolucji trójwymiarowej (przestrzenno-czasowej)
    Rys. 15.2. Interpretacja geometryczna konwolucji trójwymiarowej (przestrzenno-czasowej)

    15.3. Analiza sekwencji video – przykład

    Na rys. 15.3 pokazano przykład wykorzystania praktycznego w przetwarzaniu sekwencji obrazów (klatek). W przykładzie sygnał video podawany był z video, który odtwarzał uprzednio zarejestrowaną taśmę z nagraniem sytuacji rzeczywistej. Poszukiwany był wzorzec białego jasnego samochodu – wzorzec miał rozmiar 9×9 pikseli. Wzorzec był korelowany (korelacja to konwolucja z odpowiednio zdefiniowanym kernelem) z obszarem poszukiwań, początkowo zlokalizowanym w miejscu, w którym rozpoczyna się droga (rys. 15.3 – lewy dolny róg). W chwili pojawienia się samochodu funkcja korelacji wzorca dawała wyraźne maksimum. W miarę poruszania się samochodu maksimum funkcji korelacji podążało za samochodem. Kolejne miejsca maksimum połączone zostały krzywą i w ten sposób powstał ślad trasy przejazdu. Należy również nadmienić, że wzorzec samochodu był modyfikowany dynamicznie, tzn. uwzględniał zmiany obrazu samochodu w miarę jego przemieszczania się wzdłuż drogi. W przypadku zasłonięcia samochodu przez występujące słupy trakcyjne, maksimum funkcji korelacji wyraźnie słabło. Tym niemniej po ponownym pojawieniu się całej sylwetki samochodu można go było wyraźnie odnaleźć. Dla wartości maksimum funkcji korelacji eksperymentalnie dobrano wartość progową. Obszar poszukiwań początkowo umieszczony był w lewym dolnym rogu obrazu, a następnie po odnalezieniu wzorca, obszar ten podążał za samochodem, tak aby jego centrum pokrywało się z miejscem wystąpienia maksimum funkcji korelacji na poprzedniej klatce. Dla tego przykładu wyraźnie widać oczywiste możliwości zrównoleglenia obliczeń, np. poszukiwanie obiektu na poszczególnych klatkach osobno.

    Śledzenie obiektu obserwowanego nieruchomą kamerą
    Rys. 15.3. Śledzenie obiektu obserwowanego nieruchomą kamerą

    15.3.1. Wnioski

    Powyżej przedstawiono konwolucję dwu- i trójwymiarową jako podstawową technikę przetwarzania obrazów. Pokazano wykorzystanie systemu przy śledzeniu obiektów ruchomych na obrazach rejestrowanych przez nieruchomą kamerę. Zasygnalizowano również rozmiar problematyki przetwarzania i analizy obrazów w przypadkach ogólnych. Pokazano szerokie możliwości zrównoleglenia przetwarzania oraz wykonywania rozproszonych obliczeń na niezależnych jednostkach, potencjalnie w sieci rozległej.

    15.4. Wybrane zagadnienia implementacyjne

    W praktycznych implementacjach systemów aktywnego monitoringu występuje wiele problemów. Poniżej opisano zagadnienia związane z różnorodnością formatów plików zawierających cyfrowe zapisy wideo oraz z algorytmami stosowanymi do ich przekształcania.

    15.4.1. Formaty plików wideo

    W praktycznych zastosowaniach wykorzystuje się szereg formatów dla plików zawierających cyfrowe zapisy multimedialne (wizyjne). Aktualnie stosowanych jest bardzo wiele formatów. Wynika to przede wszystkim z wprowadzania własnych standardów przez szeroką gamę producentów sprzętu video, jak również ze zorientowania tych standardów na określone zastosowania aplikacyjne.

    Spośród rozmaitych formatów dla multimediów o charakterze przekazu wizyjnego można wymienić te najpopularniejsze:

    • AVI – format plików wideo często wykorzystywany do zapisywania filmów obrobionych w programach do obróbki wideo. Jest często używany na urządzeniach mobilnych PDA. AVI jest odmianą formatu RIFF.
    • MOV – technologia multimedialna rozwijana przez firmę Apple.
    • MPG (MPEG) – format video obsługujący kodowanie MPEG-1 oraz MPEG-2.
    • MP4 (MPEG-4) – kontener multimedialny. Oficjalne rozszerzenie pliku to .mp4, lecz w przypadku plików zawierających jedynie strumień dźwięku (np. AAC lub Apple Lossless) stosuje się również rozszerzenie .m4a.
    • ASF – format plików wideo. Format ASF wykorzystywany jest najczęściej do przechowywania strumieni danych zakodowanych za pomocą Windows Media Audio (WMA) lub Windows Media Video (WMV).
    • VCD – format zapisu cyfrowego strumienia audio-wideo na płycie kompaktowej.
    • SVCD – standard nagrywania płyt bardzo podobny do VCD. Główną różnicą między tymi jest jakość obrazu.
    • WMV (Windows Media Video) – format kompresji filmów.
    • DV (Digital Video) – format cyfrowego zapisu wizji stosowany głównie w kamerach cyfrowych DVC (Digital Video Camcorder) oraz magnetowidach cyfrowych DVCR (Digital Video Cassette Recorder).
    • FLV – format technologii Flash wykorzystywany w odtwarzaczach wideo na stronach internetowych np. YouTube. Plik .flv można odtworzyć za pomocą zwykłej przeglądarki internetowej z wtyczką Adobe Flash Player lub Gnash, a także osobnych programów, spośród których wiele udostępnianych jest bezpłatnie, np. Winamp, Moyea FLV Player, FLV Player, ALLPlayer (programy na licencji freeware), Mplayer, VLC media player (programy na licencji GPL).
    • M2TS (Blu-ray) – format zapisu filmów HD przez kamery AVCHD.
    • MKV – format przechowywania obrazu lub dźwięku w jednym pliku (kontener multimedialny).

    W realizowanych aplikacjach dotyczących monitoringu obsługiwane są najpopularniejsze z zaprezentowanych standardów dla formatów video.

    Zasadniczym komponentem jest tutaj biblioteka procedur przekształcających określone wybrane standardy do formatu umożliwiającego zautomatyzowane przetwarzanie numeryczne, czyli w praktyce konwersja do postaci opisującej poszczególne klatki przekazu na poziomie pojedynczych pikseli.

    15.4.2. Przekształcenia kontekstowe

    Operacje polegają na modyfikacji poszczególnych elementów obrazu w zależności od ich stanu i stanu ich otoczenia. Ze względu na rozmiar kontekstu mogą wymagać wielu powtarzalnych operacji, ale algorytmy są regularne i ponadto mogą być wykonywane na wszystkich punktach obrazu jednocześnie.

    Filtry wykorzystywane do analizy obrazów zakładają, że wykonywane na obrazie operacje będą kontekstowe. Oznacza to, że dla wyznaczenia jednego punktu obrazu wynikowego trzeba dokonać określonych obliczeń na wielu punktach obrazu źródłowego. Algorytm polega na obliczeniu funkcji, której argumentami są wartości pikseli z otoczenia. Otoczenie najczęściej utożsamiane jest z kwadratowym obszarem otaczającym symetrycznie aktualnie przetwarzany piksel [5].

    Paradygmat przetwarzania:
    master-slave,
    single program multiple data.
    Dane wejściowe
    sekwencja klatek n klatek o rozdzielczości x na y, przy trzech składowych RGB.
    Wynik
    sekwencja n klatek o rozdzielczości x na y, przy zapisie w składowych RGB.
    Typowe rozmiary danych
    n – długość sekwencji, typowo 24 klatki na sekundę, typowa rozdzielczość: x=800, y=600, trzy składowe koloru RGB (3 bajty).
    Nazwy instancji algorytmu
    filtry liniowe, konwolucja (splot funkcji), filtry dolnoprzepustowe, filtry górnoprzepustowe (gradient Robertsa, maska Prewitta, maska Sobela), filtry górnoprzepustowe wykrywające narożniki, filtry górnoprzepustowe wykrywające krawędzie, etc.

    15.4.3. Przekształcenia kontekstowe w dziedzinie czasu

    Algorytmy operujące na trójwymiarowej reprezentacji obrazów, gdzie trzecim wymiarem jest czas, a w praktyce określona liczba występujących po sobie klatek w sekwencji. Algorytmy te dają możliwość przekształcania kontekstowego w dziedzinie czasu, gdzie klatka wynikowa jest rezultatem przetwarzania kilku (kilkunastu) sąsiadujących ze sobą klatek. Algorytmy te również nadają się do zrównoleglenia, przy czym ich złożoność jest tutaj trójwymiarowa.

    Paradygmat przetwarzania:
    master-slave,
    single program multiple data.
    Dane wejściowe
    sekwencja klatek n klatek o rozdzielczości x na y, przy trzech składowych RGB.
    Wynik
    sekwencja n klatek o rozdzielczości x na y, przy zapisie w składowych RGB.
    Typowe rozmiary danych
    n – długość sekwencji, typowo 24 klatki na sekundę, typowa rozdzielczość: x=800, y=600, trzy składowe koloru RGB (3 bajty).
    Zastosowania
    detekcja obiektów ruchomych, filtracja tła, estymacja ruchu obiektów.

    15.5. Podsumowanie

    Zaprezentowane algorytmy z dziedziny przetwarzania obrazów są możliwe do efektywnego wykorzystania w systemie Comcute. Podane algorytmy są w zdecydowanej wielkości w pełni skalowalne. Podstawowe cechy algorytmów, takie jak rozpraszanie obliczeń oraz rozpraszanie danych, są w pełni przystosowane do równoległej praktycznej realizacji (są skalowalne).

    W dziedzinie przewarzania obrazów danymi jest zazwyczaj sekwencja video składająca się z poszczególnych klatek. Każda z klatek jest reprezentowana poprzez matrycę o określonych wymiarach (zależnych od jakości lub formatu), reprezentowana poprzez wartości pikseli (barwne lub nie). W przypadku typowego przetwarzania klatka po klatce od razu widać możliwości segmentacji danych na poszczególne klatki. Ponadto w ramach pojedynczej klatki wykonywane są operacje powtarzalne o rozmiarze kernela (rozmiar zdecydowanie mniejszy od rozmiarów klatki). Tutaj też istnieje możliwość segmentacji. W przypadku tym istotne jest rozważenie, czy rozproszenie wynikające z podzielenia będzie kompensowało zwiększone koszty komunikacyjne. Widać wyraźnie, że tego typu podejście znajduje uzasadnienie w praktycznych zastosowaniach dla systemu Comcute.

    15.6. Wykaz literatury

    1. Brudło P., Kuchciński K.: Parallel Spatio-Temporal Convolution Scheme Oriented for Hardware Real-Time Implementation, Proceedings: 23rd EUROMICRO Conference, Budapeszt, Węgry, wrzesień 1997, pp. 190-195
    2. Brudło P.: Wykorzystanie procesorów sygnałowych w przetwarzaniu obrazów, Materiały konferencyjne: Przetwarzanie Sieciowe i Rozproszone, Jastrzębia Góra, listopad 1999, Praca zbiorowa Katedry Architektury Systemów Komputerowych KASKBOOK, pp. 155-161
    3. Brudło P.: System przetwarzania i analizy sekwencji obrazów video w oparciu o sieć procesorów sygnałowych serii ADSP-21060, Materiały konferencyjne: Systemy Czasu Rzeczywistego ‚2000, Kraków, wrzesień 2000, pp. 485-494
    4. Granlund G., Knutsson H.: Signal Processing for Computer Vision, Dordrecht, Holland, Kluwer Academic Publishers
    5. Woźnicki J.: Podstawowe techniki przetwarzania obrazu, Wydawnictwa Komunikacji i Łączności, Warszawa

  • Optymalizacja równoważenia obciążeń w systemach klasy grid

    W rozdziale zaprezentowano techniki równoważenia obciążeń testowane w systemie rozproszonym Comcute o architekturze typu grid. Omówiono niezbędne uwarunkowania środowiska prowadzenia obliczeń w zestawie laboratoryjnym Politechniki Gdańskiej, a także odniesiono się do kryteriów kierunkujących równoważenie obciążeń. Przedstawiono wielopoziomową metodę równoważenia obciążeń.

    13.1. Środowisko do optymalizacji obciążenia w zestawie laboratoryjnym PG

    Optymalizacja obciążenia w systemie Comcute polega na przydziale aplikacji warstw Z, W i S do węzłów obliczeniowych w taki sposób, aby nie tylko wykorzystać specyfikę przetwarzania poszczególnych modułów pod kątem skrócenia czasu obliczeń, ale także w celu równoważenie obciążeń. W architekturze laboratoryjnego zestawu systemu Comcute skonstruowanego na Politechnice Gdańskiej w Katedrze Architektury Systemów Komputerowych WETI przewidziano 9 węzłów obliczeniowych, macierz dyskową i lokalną sieć komputerową Gigabit Ethernet. Węzły od nr 1 do 7 dedykowane są do eksploatacji głównego prototypu programistycznego napisanego w technologii programistycznej JEE.

    W systemie Comcute JEE każdy węzeł obliczeniowy zawiera dwa procesory po 6 rdzeni. 2 węzły wyposażone są w pamięć RAM o wielkości 24 GB, a pięć – 48 GB. Ponadto w każdym węźle jest dysk twardy o pojemności 3 TB. Możliwe jest zatem przetwarzanie 84 wątki jednocześnie. Komunikację między węzłami zapewnia sieć Gigabit Ethernet o przepustowości 1 Gb/s. Może być stosowana wersja 10 Gb/s lub 100 Gb/s. System wykorzystuje macierz dyskową składającą się z 8 dysków o pojemności 2 TB każdy. Na prototyp napisany w języku Java przeznaczono siedem węzłów (nr 1-7).

    System operacyjny Linux CentOS w wersji 6.1 jest zainstalowany w domenie o 50 GB pamięci na lokalnym dysku twardym. Ponadto w każdym węźle systemu Comcute JEE zainstalowano serwer NFS v3 (ang. Network File System) z protokołem do zdalnego udostępniania systemu plików. Wówczas po wysłaniu żądania przez klienta, żądanie zostaje odebrane przez serwer, a operacja jest wykonywana na dysku. Następnie potwierdzenie jest wysłane przez serwer, a klient odbiera to potwierdzenie. W rezultacie użytkownik może uzyskać dostęp do plików znajdujących się na zdalnym komputerze, a także z nich korzystać tak, jakby były na lokalnym dysku twardym w jego komputerze. Odnosi się to także do macierzy dyskowej.

    Do węzła nr 1 przydzielono następujące zasoby dyskowe:

    • 50 GB – system operacyjny;
    • 3 TB – katalogi domowe udostępniane przez NFS pozostałym komputerom linuksowym;
    • 568 GB – katalog /opt na potrzeby serwera GlassFish i stron WWW;
    • 6,4 TB – katalog /macierz podpięty z macierzy dyskowej.

    Natomiast pozostałe węzły linuksowe od nr 2 do nr 7 mają przydzielone następujące zasoby dyskowe:

    • 50 GB – system operacyjny;
    • 3 TB – katalogi domowe pobrane z serwera DNS;
    • 3,6 GB – katalog /opt na potrzeby serwera GlassFish i stron WWW;
    • 6,4 TB – katalog /macierz podpięty z macierzy dyskowej.

    W węźle nr 1 zainstalowano także serwer stron WWW Apache 2.2.15. Istotną rolę odgrywa także system zarządzania bazą danych MySQL 5.1.52 w węźle nr 1. Serwer i biblioteki klienckie MySQL umożliwiają korzystanie z serwera bazodanowego MySQL z poziomu aplikacji implementowanych dla wielu platform i języków programowania, w tym także dla języka Java.

    Reasumując, zainstalowane oprogramowanie podstawowe w węźle nr 1 to:

    • baza danych MySQL 5.1.52;
    • serwer DNS Bind 9.7.3;
    • serwer NFSv3;
    • serwer WWW Apache 2.2.15;
    • serwer WWW JEE Glassfish 3.1.1;
    • środowisko Java 1.7.0 update 2.

    Zainstalowane oprogramowanie podstawowe w pozostałych węzłach (2-7) to:

    • serwer WWW JEE GlassFish 3.1.1;
    • środowisko Java 1.7.0 update 2.

    Problem równoważenia obciążeń powinien zatem odbywać się w tym wielowarstwowym środowisku, a więc można postrzegać ten proces jako równoległe, wielowarstwowe równoważenie obciążeń w siedmiu węzłach obliczeniowych. Wyróżnić można kilka warstw równoważenia obciążeń:

    • DNS;
    • system operacyjny CentOS;
    • serwer aplikacji GlassFish;
    • poziom aplikacji S, W i Z.

    13.2. Równoważenie obciążenia na poziomie DNS

    W węźle nr 1 zainstalowano DNS BIND 9.7.3 (ang. Berkeley Internet Name Domain, poprzednio: Berkeley Internet Name Daemon), który jest popularnym serwerem DNS wykorzystywanym w systemach Linux i Unix. DNS stanowi niezmiernie ważny składnik zapewniający poprawne działanie systemu nazw w Internecie. DNS zapewnia zamianę adresów znanych użytkownikom Internetu na adresy zrozumiałe dla urządzeń tworzących sieć komputerową. Nazwa mnemoniczna, np. onet.pl, może zostać zamieniona na odpowiadający jej adres IP, np.: 123.138.144.232 Usługa DNS warstwy aplikacji w modelu TCP/IP jest związana z portem nr 53 TCP/UDP.

    Równoważenie obciążenia w DNS polega na przekazaniu żądań do różnych serwerów, mimo przydzielenia nazwy domeny do różnych adresów IP serwerów. Kiedy żądanie DNS jest skierowane do serwera DNS, to wówczas w celu ustalenia nazwy domeny, przydziela się jeden z adresów IP serwera w oparciu o strategie planowania, takie jak round-robin lub planowanie geograficzne. Następnie przekierowuje się żądanie do jednego z serwerów w grupie serwerów. Gdy domena żądania jest przydzielona do jednego z serwerów, kolejne żądania od klientów korzystających z tej samej lokalnej pamięci podręcznej serwera DNS są wysyłane do tego samego serwera.

    DNS BIND 9.7.3 zapewnia równoważenie obciążenia i jest łatwy w użyciu. Zalety to:

    • równoważenie obciążenia ruchu dla aplikacji opartych na protokole IP, w tym: HTTP, HTTPS (SSL), SSH, SMTP, IMAP, POP3, RDP (Terminal Services), DNS, LDAP, RADIUS i TFTP;

    • przekierowywanie ruchu do właściwych serwerów usług na podstawie zawartości pakietów danych (wartości nagłówka, cookies, nazwy domeny lub adresu URL);

    • mechanizm wykrywania serwerów i usług w celu dołączania nowych serwerów w systemie;

    • przepustowość do 1 Gbps.

    DNS BIND 9.7.3 jest wyposażony w mechanizm automatycznego wykrywania serwerów i narzędzia konfiguracyjne dostępne z poziomu intuicyjnego interfejsu WWW. Ponieważ serwer dystrybucyjny S może przydzielić kilka milionów zadań dziennie, to istotne jest zarządzenie tym serwerem pod względem obciążenia za pomocą DNS BIND 9.7.3. Na obciążenie serwera wpływa obciążenie związane z wykonywaniem procesów, które sterują przepływem kodu obliczeń, strumienia danych i wyników. Na to obciążenie DNS BIND 9.7.3 ma mniejszy wpływ. Ponadto na obciążenie serwera S wpływa transmisja danych między zadanym S a I, na którą DNS BIND 9.7.3 ma stosunkowo duży wpływ podczas zgłaszania się internautów do serwera S.

    Warto podkreślić, że skala obciążenia jest znacząca, gdyż jak szacuje się, podczas łamania szyfru DES, wymaga się przydzielenia ok. 64 tys. komputerów internautów, na których łamany jest już znacznie krótszy klucz o długości 40 bitów. Wówczas w ciągu kilku minut złamanie szyfru DES jest możliwe.

    Istotne jest także uwzględnienie obciążeń wynikających z interakcji między zadanym S a nadrzędnym W.

    Równoważenie obciążeń odgrywa za pomocą DNS BIND 9.7.3 zwiększy wydajność systemu rozproszonego Comcute. Może być postrzegane globalnie jako równoważenie obciążeń całego systemu Comcute ze względu na przyjęte kryterium jakości systemu lub też może być postrzegane lokalnie jako równoważenie obciążenia w warstwie W lub S.

    W styczniu 2012 roku rozpoczęto weryfikowanie na PG zalety DNS BIND 9.7.3 pod kątem współpracy z laboratoryjnym zestawem Comcute JEE. W języku Java napisano następujące aplety: aplet do wyznaczanie liczb pierwszych, aplet do łamania szyfru DES oraz aplet do kompresji plików. Algorytm do wyznaczanie liczb pierwszych posiada także implementację w języku JavaScript.

    Ponieważ na obniżenie wydajności wpływa niezbyt efektywny język implementacji zadań JavaScript, który będzie stanowił podstawowy formalizm opisu algorytmów obliczeniowych w docelowym Comcute, to zaproponowano, aby serwer dystrybucyjny S rozpoznawał, czy komputer internauty może prowadzić obliczenia w Javie, czy też konieczne jest stosowanie „wolniejszej” aplikacji napisanej w JavaScript. Wymaga to dysponowania dwiema implementacjami kodu obliczeń w Javie i JavaScript, które dostarczane są do internautów w zależności od możliwości realizacji przez komputer internauty. Po wykonaniu takich implementacji taka weryfikacji zalet DNS BIND 9.7.3 pod kątem efektywności w zakresie równoważenia obciążeń będzie możliwa.

    13.3. Równoważenie na poziomie systemu operacyjnego CentOS

    Równoważenie obciążenia obliczeniowego to podział zadań obliczeniowych w wielu różnych węzłów w klastrze, tak że cały klaster może zapewnić większą wydajność. Ten rodzaj systemów klastrowych jest również znany jako wysokiej wydajności klastry, który powinien być stosowany w ramach projektu Comcute w odniesieniu do klastrów składających się ze zbioru serwerów S, W i Z zlokalizowanych w jednym pomieszczeniu.

    Implementacja równoważenia obciążeń w systemie Comcute polega na wykorzystaniu gotowych już mechanizmów stosowanych w systemach operacyjnych, serwerach aplikacji, protokołach komunikacyjnych oraz na przygotowania oryginalnego oprogramowania aplikacyjnego. Równoważenia obciążenia systemu Comcute powinno być implementowane w osobnym węźle lub jako komponent używany na stronach internetowych. Wówczas program do równoważenia obciążenia akceptuje przychodzące żądanie HTTP i wybiera serwer S, do którego powinno ono zostać przekierowane. Równoważenie obciążenia można zaimplementować za pomocą gotowych już komponentów systemu Linux lub w oparciu o protokół HTTP.

    Na dystrybucji Linuksa CentOS zbudowano zestaw laboratoryjny Comcute i dlatego też rekomenduje się równoważenie obciążeń w oparciu o Linux Virtual Server (akronim LVS) w celu uzyskania wysokiej wydajności i wysokiej dostępności serwerów Z, W z S z wykorzystaniem technologii klastrów, co zapewnia dobrą skalowalność, niezawodność i łatwość obsługi. Architektura klastra serwerów jest w pełni przezroczysta dla użytkowników końcowych i interakcji użytkowników, jak gdyby był jednym wysokiej wydajności serwerem wirtualnym. W ramach projektu LVS dostępne są:

    • zaawansowane oprogramowanie IP do równoważenia obciążenia (IPVS);
    • równoważenie obciążenia na poziomie aplikacji (KTCPVS);
    • elementy zarządzania klastrami.

    IPVS (IP Virtual Server) wspomaga warstwę transportową (warstwa 4), równoważąc obciążenia w kernelu Linuksa. IPVS uruchomiony na komputerze równoważy obciążenia na klastrze serwerów, może on kierować żądania o usługi TCP/UDP do serwerów, a widziany jest jako wirtualny serwis pod jednym adresem IP.

    W warstwie aplikacji (7) równoważenie obciążenia na poziomie aplikacji jest przetwarzaniem żądań i dystrybucji tych żądań o dopuszczenie do serwerów opartych na różnego rodzaju treści żądania tak, że może zapewnić jakości usług dla różnych typów treści i poprawy ogólnej wydajności klastra. Jego skalowalność jest ograniczona, w porównaniu do warstwy czwartej równoważenia obciążenia. KTCPVS jest implementacją równoważenia obciążenia dla jądra Linuksa właśnie w warstwie aplikacji. Z odpowiednich modułów Apache, Lighttpd i nginx serwer WWW może zapewnić równoważenia obciążenia jako reverse proxy.

    Alternatywnym rozwiązaniem do LVS odnośnie równoważenia obciążeń jest Ultra Monkey, który koncentruje się na sieci lokalnej w zakresie równoważenia obciążenia i wysokiej dostępności usług, wykorzystujących komponenty w systemie Linux. Ultra Monkey jest również skalowalnym dla wysoko dostępnych serwerów w Internecie.

    Z kolei Red Hat Cluster Suite implementuje dwa różne rodzaje klastrów: aplikacji lub usług, a także IP Load Balancing. Klaster zapewnia możliwość równoważenia obciążenia ruchu IP w obrębie farmy serwerów.

    Dostępne w ramach projektu Linux-HA jest oprogramowanie Heartbeat na licencji GPL do zarządzania klastrami w celu uzyskania wysokiej dostępności.

    Równoważenie obciążenia w MPLS to zrównoważenie usług sieciowych opartych na informacjach na etykiecie (ang. Multiprotocol Label Switching).

    13.4. Równoważenie na poziomie serwera aplikacji GlassFish

    Kluczową rolę w środowisku Comcute odgrywa serwer aplikacji GlassFish 3.1.1, który umożliwia przechowywanie i uruchamianie aplikacji S, W, Z, aplikacja do wyznaczania liczb pierwszych, aplikacja do łamania kodu DNS czy aplikacja do badania podobieństw skompresowanych plików. GlassFish składa się z komponentów udostępnionych programiście przy pomocy specjalnego API, których zadaniem jest wspieranie programisty przy pisaniu aplikacji poprzez zwolnienie go z odpowiedzialności za elementy nie związane bezpośrednio z logiką biznesową. Przykładem takich funkcjonalności mogą być:

    • zarządzanie sesją,
    • zarządzanie transakcjami danych,
    • obsługa współdzielenia zasobów,
    • obsługa skalowalności aplikacji i load balancing.

    Architektura serwera aplikacji GlassFish zakłada obecność cienkiego klienta, który zajmuje się mało wymagającymi zadaniami, jak wyświetlanie GUI. Logika biznesowa przetwarzana jest właśnie na serwerze aplikacji. Aplikacja działająca na tymże serwerze przy pomocy udostępnionych metod komunikuje się z warstwą danych.

    Wykorzystanie serwera aplikacji niesie ze sobą wiele zalet. Architektura cienkiego klienta nie tylko zdejmuje z klienta obciążenie związane z przetwarzaniem, ale również powoduje, iż łatwiej jest zarządzać logiką biznesową, bowiem jest ona scentralizowana na jednym serwerze (bądź małej ich liczbie). Od serwera WWW klasy Apache, serwer GlassFish odróżnia bardziej zaawansowana funkcjonalność, często np. dodatkowa kontrola dostępu do bazy danych.

    Dla aplikacji webowych klasy S, W i Z, komponenty serwera GlassFish działają w tym samym węźle obliczeniowym, co serwer webowy, przeważnie wspomagając tworzenie dynamicznych stron. GlassFish udostępnia funkcjonalność znacznie wykraczającą poza generację stron webowych, jak na przykład klasteryzacja, rozwiązania fail-over oraz równoważenie obciążenia, pozwalając programiście skupienie się na rozwijaniu logiki biznesowej aplikacji.

    Główne funkcje serwera aplikacji GlassFish:

    • Spójność kodu i danych – poprzez centralizację logiki biznesowej wszystkie zmiany w aplikacji będą dotyczyły wszystkich użytkowników;

    • Scentralizowana konfiguracja – wszystkie zmiany w konfiguracji aplikacji, jak na przykład zmiana serwera bazy danych lub ustawień systemowych odbywa się centralnie;

    • Bezpieczeństwo – serwer aplikacji służy jako punkt wejścia do warstwy danych dla wszystkich użytkowników, rozdzielając potencjalnie niebezpieczną warstwę kliencką od warstwy bazodanowej i implementując mechanizmy autoryzacji i uwierzytelniania;

    • Wydajność – ograniczenie ruchu sieciowego;

    • Oszczędność– powyższe punkty mogą skutkować w redukcji kosztów organizacji rozwijającej aplikacje biznesowe;

    • Zarządzanie transakcjami – transakcja jest jednostką aktywności systemu, w której wiele zmian w zasobach aplikacji może zostać wykonanych atomowo.

    GlassFish udostępnia obsługę wielu protokołów komunikacji sieciowej. Klienci webowi komunikują się za pomocą HTTP lub HTTPS, natomiast klienci EJB porozumiewają się przy pomocy ORB (ang. Object Request Broker) poprzez protokoły IIOP i IIOP/SSL. Ponadto możliwe jest uruchomienie aplikacji będącej usługą sieciową opartą na Java API for XML-Based Remote Procedure Call (JAX-RPC).

    GlassFish umożliwia implementację usługi katalogowej obiektów za pomocą interfejsu JNDI (ang. Java Naming and Directory Interface) oraz zestawu kontraktów bezpieczeństwa zdefiniowanych dla kontenerów Java Authorization Contract for Containers.

    Zarządzanie transakcjami i dostęp do systemu zarządzania bazą danych (JDBC), wysyłanie wiadomości pomiędzy komponentami programowymi (ang. Java Messaging Service), wysyłanie wiadomości e-mail (JavaMail) oraz administracja serwerem GlassFish to kolejne ważne funkcjonalności.

    Model klient-serwer z serwerem aplikacji opiera się na architekturze wielowarstwowej, w którym warstwa pośrednicząca przyjmuje żądania cienkiego klienta, przetwarza je, komunikuje się z serwerem baz danych i zwraca klientowi wyniki w czytelnej dla niego formie. Rozwiązanie to zapewnia bezpieczeństwo, elastyczność, a także daje możliwość równoważenia obciążenia i replikacji.

    Kontenery to środowiska uruchomieniowe dostarczające usług takich jak bezpieczeństwo i zarządzanie transakcjami dla komponentów aplikacji. Kontener sieciowy zawiera część aplikacji odpowiedzialną za prezentację. Kontener logiki (EJB w JavaEE) zawiera komponenty odpowiedzialne za logikę aplikacji.

    GlassFish zapewnia klientom dostęp do aplikacji przez różne protokoły – HTTP i HTTPS dla przeglądarek, IIOP (Internet Inter-ORB Protocol) i IIOP/SSL dla klientów EJB czy SOAP. Możliwe jest wdrożenie aplikacji dostarczającej usługi sieciowej (ang. Web Service) implementowanej przez Java API for XML-Based RPC (JAX-RPC). Aplikacja lub komponent może być także klientem dla usługi sieciowej i komunikować się przez Java API for XML Registries (JAXR)

    Kontenery dostarczają usług dla aplikacji:

    • Nazewnictwo – usługa przypisuje obiekty do nazw. Aplikacja znajduje obiekt przez nazwę JNDI (Java Naming and Directory Interface).

    • Bezpieczeństwo – zestaw zasad bezpieczeństwa zdefiniowanych dla kontenerów (JACC – Java Authorization Contract for Containers).

    JDBC (Java Database Connectivity) zapewnia dostęp do baz danych, a JMS (Java Messaging Service) to metoda komunikacji pomiędzy komponentami i aplikacjami, Connector to komunikacja z systemami EIS (Enterprise Information Systems), a Server Administration – podsystem do zarządzania serwerem.

    Istnieje również nowe rozwiązanie komercyjne, pozwalające na uruchomienie zarówno aplikacji w JEE jak i .NET: Interstage Application Server powered by Windows Azure – serwer aplikacji uruchomiony w 2011 roku przez firmę Fujitsu.

    Należy podkreślić, że serwery aplikacji GlassFish ze swoimi usługami wybiegają dużo dalej niż funkcjonalności serwerów WWW (dzięki czemu programiści mogą skupić się przede wszystkim na implementacji logiki biznesowej) oferując takie usługi jak klasteryzacja, czy równoważenie obciążenia.

    GlassFish służy jako punkt wejścia do warstwy danych dla aplikacji, rozdzielając potencjalnie niebezpieczną warstwę kliencką od warstwy bazodanowej i implementując mechanizmy autoryzacji i uwierzytelniania.

    Zarządzanie wydajnością w serwerze GlassFish sprowadza się najczęściej do ograniczenia ruchu sieciowego. Zarządzanie transakcjami też jest możliwe, przy czym transakcja jest jednostką aktywności systemu, w której wiele zmian w zasobach aplikacji może zostać wykonanych atomowo.

    Duża skalowalność (obsługa klastrów) i zapewnienie zintegrowanego, zcentralizowanego zarządzania to kolejna zaleta serwera GlassFish. Obsługa standardów polega na tym, że klienty webowe komunikują się za pomocą HTTP lub HTTPS, natomiast klienty EJB porozumiewają się przy pomocy ORB (ang. Object Request Broker) poprzez protokoły IIOP i IIOP/SSL. Istotne jest także zapewnienie środowiska do tworzenia, testowania, wdrażania i zarządzania aplikacjami, a także dostarczenie biblioteki klas (API).

    Architektura serwera aplikacji zakłada obecność cienkiego klienta, który zajmuje się mało wymagającymi zadaniami, jak wyświetlanie GUI. Logika biznesowa przetwarzana jest właśnie na serwerze aplikacji. Aplikacja działająca na tymże serwerze przy pomocy udostępnionych interfejsów. Funkcjonalność serwerów na różne platformy definiują odpowiednie specyfikacje (np. w przypadku Java EE 6 specyfikacje JSR-316).

    Z konieczności współpracy z wieloma typami rozwiązań wynika jedna z najistotniejszych cech serwera GlassFish – otwartość na standardy wymiany informacji. Tylko dzięki temu możliwe jest integrowanie różnych rozwiązań informatycznych.

    13.5. Równoważenie obciążeń na poziomie aplikacji

    Na poziomie aplikacji możliwe jest równoważenia obciążeń w systemie Comcute za pomocą opracowanej metody w [1]. Jeżeli przydział zadań obliczeniowych i pakietów danych do serwerów w systemie Comcute minimalizuje łączne obciążenie, to może wystąpić sytuacja skupienia modułów (rozumianych jako zadania obliczeniowe lub pakiety danych) w wybranym węźle obliczeniowym. Ten węzeł będzie zatem najbardziej obciążony pod względem liczby przydzielonych zadań, a pozostałe węzły mogą być obciążone w znacznie mniejszym stopniu.

    Przyjęto, że miarą obciążenia serwera w systemie Comcute jest Zmax – łączny czas przetwarzania danych i obciążenia zewnętrzną komunikacją w najbardziej wykorzystywanym serwerze. W wyniku przydzielenia modułów do i-tego węzła serwer w nim usytuowany jest zajęty realizacją tych modułów w czasie Zi(x), który nazywamy czasem zajętości serwera Z lub W przydzielonego do i-tego węzła. Wartość czasu Zi(x) wyznacza się w następujący sposób:

    wzór
    (1)

    gdzie: I – liczba węzłów w systemie Comcute, aktualnie I=7; wzór – binarny wektor przydziału dystrybuowanych zadań i pakietów danych do serwerów, v – nr modułu (zadania lub pakietu danych); wzór – binarny wektor odwzorowujący hosty na węzły obliczeniowe, i – nr węzła, j – nr hosta; tvj – szacowany czas wykonania modułu mv na hoście pj, J – liczba rodzajów serwerów (przyjmujemy J=2, serwer typu S ma numer 1, a W – 2)

    Istotnym obciążeniem podsystemu komunikacyjnego i-tego węzła jest wysyłanie i odbiór danych. Czas Zi(x) nadawania i odbioru danych w i-tym serwerze wyznacza się, jak niżej:

    wzór
    (2)

    Obciążeniem i-tego węzła nazywamy łączny czas zajętości serwera przydzielonego do i-tego węzła oraz czas nadawania i odbioru danych w i-tym węźle. Obciążenie i-tego węzła Zi+(x) dla zadanego przydziału x wyznaczamy w następujący sposób:

    wzór
    (3)

    Serwer o największym obciążeniu Zi+(x) stanowi „wąskie gardło” systemu Comcute. Im mniejsze jest jego obciążenie, tym bardziej moduły są zdecentralizowane. Ponadto mniej obciążony serwer generuje mniejszy ruch danych w sieci komputerowej. Dlatego minimalizacja największego obciążenia w węzłach systemu Comcute prowadzi do równoważenia obciążeń. Maksymalne obciążenie węzła dla zadanego przydziału modułów do serwerów x wyraża się następującą formułą:

    wzór
    (4)

    Jeżeli moduły zostaną przesunięte z hosta w najbardziej zajętym węźle na komputery obciążone w znacznie mniejszym stopniu, to zostanie zmniejszona zajętość najbardziej obciążonego serwera, co skutkuje dążeniem do wyrównania obciążenia wszystkich węzłów w systemie. Postulat równoważenia obciążenia w systemie Comcute może być uwzględniony przez funkcję celu Zmax lub też poprzez wprowadzenie dodatkowego ograniczenia, aby Zmax(x) £ Tgr, gdzie Tgr reprezentuje założone największe dopuszczalne obciążenie serwera w systemie Comcute. Sformułowano zadanie minimalizacji funkcji Zmax umożliwiające równoważenie obciążeń w systemie Comcute:


    Dla danych wzór, wzór należy wyznaczyć x*,takie że

    wzór
    (5)

    gdzie:

    • wzór
    • wzór
    • wzór

    Zadanie optymalizacji (5) charakteryzuje się skończonym zbiorem rozwiązań dopuszczalnych oraz nieliniową funkcją celu. Dla V31, J=1 i I=7 istnieje co najmniej jedno rozwiązanie dopuszczalne. Liczba przydziałów modułów do komputerów wynosi 7V, rośnie wykładniczo wraz ze wzrostem liczby modułów oraz liniowo wraz ze wzrostem liczby węzłów.

    Zbiór możliwych wariantów w problemie (5) dla reprezentacji binarnej przydziałów modułów do komputerów zawiera 27 (V+1)alternatyw. Przyjmując reprezentację całkowitoliczbową przydziału modułów do hostów, uzyskuje się rozwiązanie dopuszczalne, a zbiór rozwiązań dopuszczalnych zawiera 7 V przydziałów.

    Do rozwiązania zadania (5) zastosowano algorytm przeszukiwania tabu TSZmax [1]. Optymalne przydziały uzyskano dla instancji o 32 binarnych zmiennych decyzyjnych (V=11, I=2, J=5) dla 100 różnych punktów startowych.

    Wraz ze wzrostem rozmiaru zadania średnia liczba wyznaczanych rozwiązań optymalnych L* zaczęła maleć. Dla instancji o 36 binarnych zmiennych decyzyjnych (V=10, I=3, J=2) względny błąd maksymalny Bmax wyniósł 9,4%, średni błąd względny B – 2,5%, a w 41% wypadków wyznaczono przydziały optymalne. Ta instancja cechuje się ponad 68 miliardami binarnych przydziałów modułów do komputerów, a zbiór rozwiązań dopuszczalnych zawiera 472 392 przydziały dopuszczalne. Czas obliczeń programu implementującego algorytm TSZmax wyniósł 0,4 sekundy. Program uruchamiano w środowisku Matlab na komputerze klasy PC. Algorytm TSZmax w ciągu minuty umożliwia wyznaczenie rozwiązań o wyższej jakości niż algorytm przeglądu przydziałów dopuszczalnych w ciągu godziny.

    Dla instancji o 60 binarnych zmiennych decyzyjnych (V=12, I=4, J=3) w wyniku 100 eksperymentów numerycznych wyznaczono wynik referencyjny, w odniesieniu do którego względny błąd maksymalny Bmax wyniósł 7,2%, średni błąd względny B był równy 5,2%, a w 6% wypadków wyznaczono przydziały referencyjne. Ta instancja cechuje się ponad 1018 binarnymi przydziałami modułów do komputerów, a zbiór rozwiązań dopuszczalnych zawiera 1 358 954 496 przydziałów dopuszczalnych. Czas obliczeń programu implementującego algorytm TSZmax wyniósł 20 sekund.

    Dla instancji o 100 binarnych zmiennych decyzyjnych (V=20, I=4, J=5) w wyniku 100 eksperymentów numerycznych wyznaczono wynik referencyjny, w odniesieniu do którego względny błąd maksymalny Bmax wyniósł 4,7%, średni błąd względny B był równy 2,1%, a w 5% wypadków wyznaczono przydziały referencyjne. Ta instancja cechuje się ponad 1030 binarnymi przydziałami modułów do komputerów, a zbiór rozwiązań dopuszczalnych zawiera prawie 7´1014 przydziałów dopuszczalnych. Czas obliczeń programu implementującego algorytm TSZmax wyniósł 115 sekund.

    Powyższe eksperymentalne wyniki weryfikują pozytywnie hipotezę, że można równoważyć obciążenia w systemie siedmiowęzłowego Comcute JEE za pomocą algorytmu obliczeniowego TSZmax, ale czas potrzebny na wyznaczenie takiego obciążenia jest na poziomie kilku minut

    13.6. Symulowanie równoważenia obciążeń za pomocą oprogramowania

    Interesujące podejście do oszacowania równoważenia obciążeń opiera się na wykorzystaniu specjalistycznego oprogramowania symulującego obciążenie systemu. Oprogramowanie to służy do badania obciążenia (w tym równoważenia obciążenia), testowania, a także badania projektów systemów rozproszonych w zależności od założonych warunków początkowych lub parametrów technicznych. Daje możliwość zbadania systemu Comcute pod kątem jego modyfikacji.

    Oprogramowanie OPNET umożliwia jest zarządzanie wydajnością aplikacji, a także planowanie i projektowanie zestawu laboratoryjnego Comcute. Zarządzanie obejmujące monitorowanie pracy, analizę działania aplikacji, zaawansowane rozwiązywanie problemów, planowanie wydajności oraz analizy systemu rozproszonego. Ponadto dostępne są opcje skutecznego zarządzania wydajnością aplikacji w warunkach zestawu laboratoryjnego Comcute. Wydajne, intuicyjne środowisko analityczne umożliwia certyfikację aplikacji przed ich wdrożeniem, sprawdzanie skutków zaplanowanych zmian oraz przyspieszenie procesu rozwiązywania problemów związanych z wydajnością aplikacji produkcyjnych.

    Istotną funkcjonalnością jest zbieranie informacji przez agentów programistycznych. Warto także zasygnalizować możliwość analizowania informacji na temat pakietów sieciowych poparte automatycznym prowadzeniem statystyk. Intuicyjne, zaawansowane schematy graficzne umożliwiają wizualizację działania aplikacji. Z punktu widzenia badania obciążenia istotne są raporty diagnostyczne umożliwiające określenie wąskich gardeł wydajności i źródeł opóźnień czasu odpowiedzi w otoczeniu internetowym. Możliwe jest szybkie i dokładne przewidywanie czasów odpowiedzi aplikacji w środowiskach wirtualnych obejmujących wiele klientów, serwerów i aplikacji, co jest szczególnie dogodne dla systemu Comcute.

    Planowanie wdrażania optymalizacji systemu Comcute umożliwia sprawdzania wpływu proponowanych modyfikacji na czas reakcji w zoptymalizowanych środowiskach. Rozwiązanie pozwala organizacjom dużo skuteczniej planować wdrażanie urządzeń optymalizujących sieci poprzez identyfikację lokalizacji i aplikacji, które mogłyby przynosić możliwie największe korzyści.

    Symulacje pozwalają przewidzieć zachowanie infrastruktury w różnych sytuacjach. Środowisko uwzględnia skomplikowane relacje pomiędzy poszczególnymi elementami otoczenia internetowego (warstwy I w Comcute) i dostarcza szerokie spektrum informacji niezbędnych do oceny wydajności aplikacji i pracy Comcute. Dzięki tym informacjom możliwe jest planowanie efektywnych systemów informatycznych, ich konfiguracja, rozbudowa i diagnostyka.

    Podstawową korzyścią ze stosowania tego oprogramowania jest uniknięcie eksperymentów na „żywym organizmie”, jakim jest demonstrator Comcute.

    Możliwe jest także planowanie pojemności serwerów przy zastosowaniu analizy konfiguracji i obciążeń roboczych systemów, a także prognozowania skutków wdrożeń nowych aplikacji, zmian w profilach obciążeń roboczych i efektów dostrajania wydajności. Wykorzystując integrację z narzędziami do monitorowania wydajności serwerów, można zaplanować wydajność serwerów, aby sprostać rozrostowi systemu, konsolidacji i wirtualizacji serwerów, a także wdrożeniom kolejnych aplikacji.

    Można symulować wbudowane specyficzne dla konkretnych producentów systemy z wartościami opisującymi ich wydajność dla testu SPEC (ang. Standard Performance Evaluation Corporation), a także skonfigurowania własnych serwerów. Ważna cecha to integracja ze statystykami o wydajności serwerów z wiodących na rynku rozwiązaniami do monitorowania: CA Unicenter, Network and Systems Management, HP OpenView Performance Agent i HP OpenView Performance Manager, BMC Performance Assurance Perform Collector i Microsoft Windows Vista/7 Perfmon.

    Symulacja systemu Comcute umożliwia opracowanie charakterystyki obciążenia roboczego aplikacji przy użyciu zaawansowanych algorytmów filtrujących. Ocena wydajności architektury aplikacji to kolejna interesująca opcja z punktu widzenia symulacji środowiska Comcute, co pozwala przewidzieć skutki odnośnie wydajności, jakie mogą nastąpić z powodu zmian architektury aplikacji w czasie jej projektowania. Symulacja bada, czy możemy skonsolidować aplikacje z różnych systemów na jednej platformie oraz jak mamy skonfigurować serwer, żeby wspierał systemy wirtualne.

    Można oszacować:

    • pojemność i na ile ona wystarczy,
    • ile pojemności powinniśmy dodać do naszych systemów,
    • w jaki sposób wzrost obciążenia roboczego będzie wpływał na poziomy dostępności aplikacji,
    • czy mamy wystarczającą pojemność dla każdej warstwy architektury aplikacji?

    13.7. Równoważenie obciążeń w węźle nr 9

    Węzeł nr 9 to serwer z systemem operacyjnym Windows 2008 Server R2. Zasoby dyskowe obejmują:

    • dysk twardy;
    • 199 GB – system operacyjny;
    • 3,4 TB – dysk twardy na pozostałe rzeczy, prototyp Comcute itp.

    Zainstalowane oprogramowanie:

    • serwer WWW IIS 7.0
    • wtyczka pGina 2.1.1 – do autoryzacji użytkowników z LDAP
    • XenCenter – do zarządzania maszynami wirtualnymi na serwerze poligon,
    • szczegóły podam później, jak to przetestujemy

    Dla aplikacji napisanych na platformie .NET za serwer aplikacji może służyć odpowiednio skonfigurowany serwer IIS7. Składa się on z modułów podzielonych na kategorie. Moduły te spełniają podstawową i rozszerzoną funkcjonalność, jaką powinien zapewniać serwer aplikacji. Kategorie podziału to modułów to:

    • moduły HTTP,
    • moduły bezpieczeństwa,
    • moduły treści,
    • moduły kompresji,
    • moduły cache,
    • moduły rejestrowania danych i diagnozowania,
    • moduły zarządzania rozszerzeniami,
    • moduły rozszerzające.

    Warto także wspomnieć o istnieniu serwerów aplikacji przeznaczonych na inne platformy niż JEE i .NET, jak na przykład Zend Server dla aplikacji napisanych w PHP.

    13.8. Podsumowanie

    Kluczowe podejście do implementacji równoważenia obciążeń w systemie Comcute polega na doborze i implementacji mechanizmów równoważenia obciążeń stosowanych w protokołach komunikacyjnych lub oprogramowaniu aplikacyjnym. Równoważenia obciążenia systemu Comcute zaimplementowano na hoście oraz jako komponent używany na stronach internetowych.

    Wielopoziomowe równoważenie obciążeń dotyczy następujących poziomów:

    • DNS BING;
    • systemu Linux CentOS;
    • serwer aplikacji GlassFish
    • aplikacji za pomocą algorytmu TZmax;

    Wskazane jest przed modyfikacją systemu Comcute stosować symulację komputerową.

    Na poziomie systemu operacyjnego Linux Virtual Server zapewnia dobrą skalowalność, niezawodność i łatwość obsługi w wyniku zastosowania następujących aplikacji:

    • zaawansowane oprogramowanie IP do równoważenia obciążenia (IPVS);
    • oprogramowania równoważenie obciążenia (KTCPVS);

    Ponadto za pomocą modułów Apache o nazwie Lighttpd i nginx serwer WWW może zapewnić równoważenie obciążenia jako reverse proxy.

    Równoważenie obciążeń w systemie Comcute może być postrzegane globalnie jako równoważenie obciążeń całego systemu ze względu na przyjęte kryterium jakości systemu (za pomocą algorytmu TZmax) lub też może być postrzegane lokalnie jako równoważenie obciążenia w obszarze aplikacji W, S lub I.

    13.9. Wykaz literatury

    1. J. Balicki: Algorytmy ewolucyjne i tabu search do optymalizacji przydziałów modułów programistycznych w rozproszonych systemach komputerowych. Wyd. AMW, Gdynia 2000
    2. Kaskbook: Serwery aplikacji, Gdańsk-Frombork 2002;
    3. Kaskbook: Aplikacje rozproszone i systemy internetowe, Gdańsk-Stawiska 2006;
    4. http://download.oracle.com/docs/cd/E19159-01/819-3671/ablat/index.html, marzec 2012
    5. http://en.wikipedia.org/wiki/Application_server, marzec 2012
    6. http://learn.iis.net/page.aspx/101/introduction-to-iis-architecture/, 2012
    7. http://technet.microsoft.com/pl-pl/library/cc772115%28WS.10%29.aspx, 2012
    8. http://www.bestpricecomputers.co.uk/glossary/application-server.htm, 2012
    9. http://www.cc.com.pl/docs/serw_aplikacji-98.pdf, marzec 2012;
    10. http://www.fujitsu.com/global/services/software/windows-azure/, marzec 2012

  • Mechanizmy bezpieczeństwa w systemie Comcute

    Celem niniejszego dokumentu jest wyróżnienie podstawowych problemów związanych z bezpieczeństwem przetwarzania w systemie utrzymania wielkiej mocy obliczeniowej w sytuacjach kryzysowych Comcute. Ponadto na przykładzie architektury systemu modelowego będą przedstawione mechanizmy bezpieczeństwa przydatne do zastosowania w projekcie.

    12.1. Założenia i wymagania

    System laboratoryjny służy do zbadania możliwości rozproszenia obliczeń wymagających dużej mocy na komputery zlokalizowane w wewnętrznej sieci lokalnej (laboratorium) lub w Internecie. Model systemu laboratoryjnego (wg zamierzeń projektantów) może stać się prototypem systemu docelowego. Z tego względu mechanizmy bezpieczeństwa odnoszące się do prototypu mają także takie same znaczenie jak w przypadku systemu docelowego.

    Jednakże niezbędne jest poczynienie jednej zasadniczej uwagi. O ile system laboratoryjny pracuje w środowisku zamkniętym (symulując mechanizmy działania systemu docelowego), to system docelowy na różnych poziomach będzie dostępny poprzez Internet. Ponadto system docelowy zapewne będzie przechowywał informacje pochodzące od swoich klientów. Z tego względu jest niezbędne zaplanowanie, opracowanie i wdrożenie polityki bezpieczeństwa. Polityka bezpieczeństwa w postaci dokumentu zatwierdzonego przez zarząd organizacji (właściciela systemu docelowego) powinna być udostępniania klientom jako pewnego rodzaju gwarancja jakości właściwego (oczekiwanego, zgodnego z przepisami i normami) postępowania z danymi klientów. Taki dokument powinien zawierać następujące elementy [1, 4, 6, 9, 10]:

    1. Postanowienia ogólne, podstawy prawne, słownik pojęć;

    2. Zasady identyfikacji i uwierzytelniania;

    3. Zakres świadczonych usług;

    4. Opis zasobów organizacji udostępnianych w ramach systemu obliczeniowego;

    5. Analiza ryzyka względem kosztów zabezpieczeń i spodziewanych korzyści;

    6. Wymagania operacyjne bezpieczeństwa (czynności stron, protokoły komunikacji, forma dostarczenia usługi, itp.);

    7. Środki bezpieczeństwa dla spełnienia wymagań operacyjnych;

    8. Zarządzanie bezpieczeństwem (kontrole, audyty, zmiany), polityki względem personelu i klientów.

    Przyjmijmy założenie, że w systemie [2] będą pracować następujące rodzaje użytkowników:

    • administratorzy konfiguracji;
    • administratorzy bezpieczeństwa – zarządcy uprawnień, ról, itp.;
    • operatorzy systemu (konfiguracja zadań od klientów, nadzór nad przebiegiem obliczeń);
    • klienci – zleceniodawcy obliczeń.

    W zależności od liczby użytkowników należy rozważyć różne modele kontroli dostępu. Dla małej liczby (kilkaset) można rozważyć wprowadzenie modelu restrykcyjnego (np. BLP – MAC+NTK) [6] lub łagodniejszego (DAC z separacją obiektów) [5,6] . Dla dużej liczby użytkowników (>1000) kosztowny we wprowadzeniu, ale łatwy w zarządzaniu jest model RBAC [5].

    12.2. Zarządzanie bezpieczeństwem informacji

    Ogólny model warstwowy zarządzania bezpieczeństwem można przedstawiono w tab. 12.1.

    Tab. 12.1. Warstwy ogólnego systemu zarządzania bezpieczeństwem

    Zarządzanie bezpieczeństwem
    (aplikacje, bazy danych, EDE, e-mail, itp.)


    Agenci bezpieczeństwa, Protokoły bezpieczeństwa
    (uwierzytelnianie, zarządzanie kluczami, itp)


    Usługi bezpieczeństwa
    (poufność, integralność, niezaprzeczalność, itp.)


    Mechanizmy bezpieczeństwa
    (podpis cyfrowy, uwierzytelnianie)


    Moduły podstawowe
    (algorytmy, tryby pracy)


    W ramach niniejszego rozdziału przedyskutowano elementy z warstwy 3 (usługi bezpieczeństwa) wraz z mechanizmami (warstwa 2 – powszechnie znane i opracowane) i częściowo protokoły bezpieczeństwa (warstwa 4). Elementy zarządzania bezpieczeństwem muszą być powiązane z polityką bezpieczeństwa (której tu nie opisujemy), natomiast podstawowe moduły bezpieczeństwa (algorytmy, tryby pracy, generatory kluczy, itp.) są powszechnie znane i opracowane [3,4,5,6]. Objaśnimy tu jedynie dwa podstawowe protokoły służące do budowy podstawowych mechanizmów bezpieczeństwa. Pierwszy z nich to protokół przesyłania wiadomości zaszyfrowanej łącznie z sesyjnym kluczem szyfrującym [3,4,5,6]. Celem tego protokołu jest zapewnienie poufności treści przesyłanej wiadomości, a także wiarygodności jej odbiorcy. Przebiega on następująco:

    1. Nadawca przygotowuje wiadomość M, losuje klucz sesyjny K i tworzy szyfrogram CK(M) z użyciem dobrej jakości symetrycznego algorytmu szyfrującego.

    2. Nadawca pobiera z zaufanej bazy danych klucz publiczny odbiorcy Opu bądź wydobywa go z certyfikatu podpisanego przez zaufanego wystawcę, a następnie szyfruje klucz sesyjny, używając tego samego symetrycznego algorytmu szyfrującego co w p. A pracującego w trybie ECB [3]. Powstaje dodatkowy szyfrogram COpu(K), który dołącza do szyfrogramu CK(M) i wysyła to wszystko odbiorcy.

    3. Odbiorca najpierw odszyfrowuje klucz sesyjny K z szyfrogramu, używając do odszyfrowania klucz prywatnego Opr, występującym w parze z kluczem publicznym Opu i otrzymuje K=DOpr(COpu(K)).

    4. Następnie odbiorca odszyfrowuje wiadomość M, używając uzyskanego w p. C klucza sesyjnego: M=DK(CK(M))

    Drugim podstawowym protokołem jest podpis elektroniczny, będący tzw. załącznikiem wiadomości. Ma on następujący przebieg [4,11]:

    1. Nadawca przygotowuje wiadomość M, oblicza skrót wiadomości H(M), a następnie, używając określonego schematu podpisu elektronicznego i prywatnego klucza podpisującego KS, oblicza podpis SKs(H(M)).

    2. Nadawca pobiera wiadomość M, dołącza do niej podpis S(H(M)) i wysyła to wszystko odbiorcy.

    3. Nadawca pobiera z zaufanej bazy danych klucz publiczny nadawcy KSpu bądź wydobywa go z certyfikatu podpisanego przez zaufanego wystawcę, a następnie wylicza wartość skrótu otrzymanej wiadomości H(M’) i używa obu tych wielkości w procedurze weryfikacji poprawności podpisu elektronicznego.

    4. Jeśli podpis jest poprawny (np. dla schematu RSA skrót wiadomości odebranej H(M’) jest zgodny ze skrótem H(M) odszyfrowanym z podpisu z użyciem klucza publicznego nadawcy KSpu), to akceptuje wiadomość. W przeciwnym wypadku wiadomość jest odrzucana jako pochodząca z niewiadomego źródła.

    Infrastruktura klucza publicznego PKI [4,11] to sieć serwerów wystawiających certyfikaty CA (Certification Authority), serwerów rejestrujących użytkowników RA (Registration Authority) wraz z polityką bezpieczeństwa określającą działania i procedury związane z zarządzaniem certyfikatami kluczy publicznych. Certyfikat klucza publicznego to struktura danych podpisana przez wystawcę certyfikatu. Te podpisane dane zawierają co najmniej dane ubiegającego się o certyfikat (a zatem posiadacza klucza prywatnego do pary z tym umieszczonym w certyfikacie), jego klucza publicznego, identyfikatora certyfikatu, danych i podpisu wystawcy. Certyfikat może ponadto zawierać wiele dodatkowych danych: datę wystawienia i okres ważności, przeznaczenie certyfikatu (kluczy), wersję standardu, ograniczenia stosowania, delegacje użycia, itp. Niezwykle istotne jest stwierdzenie, że certyfikat klucza publicznego de facto bezwzględnie łączy ze sobą użytkownika z jego kluczem prywatnym, którego oczywiście ujawnić nie można. Dzięki temu, wykorzystując klucz publiczny zawarty w certyfikacie, możemy zweryfikować autentyczność wszelkich czynności wykonanych przez użytkownika z użyciem jego klucza prywatnego (do pary z tym opublikowanym w certyfikacie) [11].

    12.3. Bezpieczeństwo interfejsu: klient zewnętrzny – system Comcute

    W tym punkcie będą opisane aspekty bezpieczeństwa interfejsu klienta – czyli warstwy komunikacji warstwy W ze światem zewnętrznym [2]. Zgodnie z dokumentem pt. „Architektura systemu – wymagania od strony klienta”, ten interfejs powinien pozwolić na realizację następujących czynności:

    • zdefiniowanie problemu wraz z niezbędnymi danymi i określeniem parametrów,
    • zdefiniowanie kodów programów niezbędnych do rozproszonego wykonania obliczeń w systemie Comcute,
    • odczytanie wyników i statusu wykonywanego zadania (kodu poprawności),
    • ewentualnie odczytanie informacji o kompletności wyników.

    Typowe zagrożenia pojawiające się w tym obszarze systemu to [3,5,6]:

    • podsłuch komunikacji – naruszenie poufności (bierny atak),
    • zniszczenie, modyfikacja komunikacji, podszywanie się, itp. (ataki czynne),
    • analiza ruchu.

    Mamy co najmniej trzy alternatywne sposoby komunikacji klienta z systemem Comcute:

    1. poprzez klasyczny interfejs użytkownika – formularz na stronie WWW systemu,
    2. jako usługa sieciowa, opublikowana i dostępna jedynie dla wybranych klientów,
    3. inny sposób komunikacji – dowolnym bezpiecznym kanałem (osobiście, poczta klasyczna, itp.).

    W zależności od sposobu komunikacji możemy wskazać tu następujące mechanizmy niezbędne do zachowania minimum bezpieczeństwa:

    1. w przypadku interfejsu www – tunel kryptograficzny SSL/TLS [5] oraz silne uwierzytelnianie (oprócz loginu i hasła dodatkowo np. protokół ZK – Zero Knowledge z wykorzystaniem kart inteligentnych) [3]. Ponadto warto zastanowić się nad dodatkowymi restrykcjami w zakresie przyjmowania ruchu sieciowego poprzez taką konfigurację zapory ogniowej, by akceptować połączenia tylko z grupą wybranych adresów IP. SSL i zapora ogniowa chronią przed podsłuchem i modyfikacją komunikacji, ale nie chronią przed analizą ruchu.

    2. W przypadku usługi sieciowej – jej opublikowanie podlega restrykcjom zawartym w opisie standardu OASIS opisującym cechy i wymagania dla rejestrów UDDI [7], a udostępnianie usługi muszą być chronione podobnie jak w p. a. Nie chroni to niestety przed analizą ruchu.

    3. Inny sposób komunikacji (np. osobiście) może zapewnić ochronę przed analizą ruchu. Dodatkowo usługę obliczeniową będzie konfigurował i wdrażał operator – pracownik właściciela systemu Comcute. Może on uruchamiać wiele obliczeń i dla każdego z nich dobierać różne opóźnienie czasowe chwili wystartowania, więc nie będzie dokładnie wiadomo, dla kogo te obliczenia są wykonywane. W tej sytuacji mamy także ochronę przed modyfikacją i podsłuchem za pomocą tych samych środków (SSL, uwierzytelnianie operatora).

    12.4. Bezpieczeństwo warstwy serwerów W

    W tym punkcie opisano aspekty bezpieczeństwa warstwy serwerów W (węzłów wewnętrznych systemu) zajmującej się zarządzaniem zadaniami obliczeniowymi zleconymi przez klienta zewnętrznego bądź operatora. Zgodnie z dokumentem pt. „Architektura systemu – problemy i koncepcje” [2], w tej warstwie są realizowane następujące czynności:

    • przyjmowanie zlecenia w postaci kodu i danych klienta oraz dodatkowych wymagań obliczeniowych,

    • partycjonowanie danych,

    • wyznaczenie kryteriów wykonalności (zakończenia) zadania,

    • ustanowienie ewentualnego arbitra oceniającego postępy w obliczeniach oraz rozstrzygającego o ważności wyników,

    • ewentualne przekształcenie kodu zleceniodawcy do postaci wykonywalnej akceptowalnej przez aplikacje internautów,

    • gromadzenie wyników obliczeń dla każdego zadania.

    Z powyższego zestawienia wynika, że warstwa serwerów W przechowuje kluczowe dane z punktu widzenia klienta zewnętrznego. Przyjmijmy dodatkowe założenie, że może być więcej grup serwerów W niż jedna, umiejscowionych w rozłącznych sieciach lokalnych. Każda taka grupa może współpracować np. z wybraną grupą serwerów S. Mogące się zmaterializować zagrożenia to: naruszenie spójności przechowywanych danych (nieuprawniona zmiana, zniszczenie), podsłuch (podgląd wyników oraz informacji, dla kogo te obliczenia są wykonywane). Z tego względu ochrona tych danych jest bardzo ważna i należy ją zaplanować na kilku poziomach:

    • Sieć lokalna, zawierająca serwery grupy W powinna być chroniona zaporą ogniową tak skonfigurowaną, że będzie akceptować połączenia zewnętrzne tylko ze ściśle zdefiniowanymi adresami IP.

    • Wszystkie połączenie pomiędzy serwerami W są realizowane w tunelu SSL z obustronnym uwierzytelnianiem.

    • Powinny być zapewnione mechanizmy transakcyjne w dostępie do współdzielonej bazy danych albo powinna być zapewniona pełna replikacja (kopie bazy danych w każdym węźle W), w miarę możliwości synchroniczna [8].

    • Dostęp do baz danych ograniczony tylko dla lokalnych aplikacji i użytkowników serwerów W i ewentualnie także serwerów S systemu laboratoryjnego.

    • Dostęp do serwerów W powinien być ograniczony jedynie dla uwierzytelnionych i autoryzowanych użytkowników.

    12.5.Bezpieczeństwo komunikacji pomiędzy warstwą serwerów W a serwerami S

    W tym punkcie zostały opisane aspekty bezpieczeństwa komunikacji warstwy W z serwerami S związane z dystrybucją podzadania obliczeniowego. Zgodnie z dokumentem pt. „Architektura systemu – problemy i koncepcje” [2], w tej warstwie są realizowane następujące czynności:

    • Wystawienie zleceń obliczeniowych przez serwer W dla serwera S.
    • Odbieranie wyników obliczeń od serwera S przez serwer W.

    Możliwe zagrożenia to: zniszczenie bądź zmiana treści komunikacji (kodu i danych do obliczeń), podszycie się, przechwycenie i zamiana (atak Man-in-the-Middle) komunikacji. Z tego względu ochrona komunikacji W–S powinna obejmować:

    • Zapewnienie spójności i autentyczności przesyłanych zleceń obliczeniowych poprzez użycie podpisu elektronicznego [3].

    • Ukrycie komunikacji albo w tunelu SSL, albo poprzez zastosowanie protokołu przesyłania zaszyfrowanych komunikatów wraz z zaszyfrowanym kluczem sesyjnym [3].

    • W celu obrony przed ewentualnym podszyciem się użycie stosownego zarządzania kluczami publicznymi – infrastruktury PKI – zarządzającej certyfikatami kluczy publicznych [11].

    12.6. Bezpieczeństwo warstwy serwerów S i komunikacji pomiędzy warstwą serwerów S a serwerami internautów I

    W tym punkcie zostały opisane aspekty bezpieczeństwa warstwy serwerów S (węzłów usługowych dostawców WWW), zajmującej się zarządzaniem podzadaniem obliczeniowym zleconym przez serwer W. Zgodnie z dokumentem pt. „Architektura systemu – problemy i koncepcje” [2], w tej warstwie są realizowane następujące czynności:

    • Przekazywanie podzadania obliczeniowego (lub wskaźnika na podzadanie obliczeniowe umieszczone na innym serwerze, np. reklamowym) przez serwer S internaucie I.

    • Odbieranie przez serwer S wyników obliczeń podzadania od internauty I albo bezpośrednio, albo pośrednio – są one przekazywane do serwera reklamodawcy, a serwer S otrzymuje wówczas co najwyżej powiadomienie, że obliczenia podzadania ukończono.

    • Przekazywanie przez serwer S serwerowi W wyników bezpośrednio albo przekazywanie informacji o tym, że wyniki są dostępne na innym serwerze, np. reklamodawcy.

    Należy wyraźnie podkreślić, że komunikacja pomiędzy komputerem internauty I a serwerem S odbywa się poza wszelką kontrolą serwerów W (i oczywiście całego systemu Comcute). Nie można wymusić obowiązkowego szyfrowania treści podzadania (kodu i danych) bez określonej umowy pomiędzy właścicielem systemu Comcute, a właścicielem serwera S i/lub serwera reklamodawcy. W tej sytuacji komunikacji pomiędzy serwerem S a komputerem I zagrażają typowe ataki internetowe, a szczególnie podsłuch i analiza ruchu. Przed naruszeniem spójności treści komunikacji chroni podpis elektroniczny.

    Wymaga poruszenia jeszcze jeden aspekt – z użyciem jakiego klucza (umieszczonego w certyfikacie klucza publicznego) poprawność komunikacji ma być weryfikowana. Aby uchronić się przed koniecznością każdorazowego zapytania internauty o akceptację certyfikatu klucza publicznego weryfikującego poprawność podpisu, tenże certyfikat klucza publicznego musi być wystawiony przez CA (Certification Authority) akceptowany automatycznie przez przeglądarki. Jest to warunek konieczny w sytuacji, jeśli nie chcemy, by uwaga właściciela komputera nie była skierowana na ten fakt bądź niepotrzebnie angażowała jego uwagę.

    12.7. Niezbędna infrastruktura PKI

    Z przedstawionych rozważań wynika, że będą potrzebne co najmniej dwie infrastruktury PKI:

    • Certyfikat klucza publicznego pochodzący od zewnętrznego, akceptowanego automatycznie przez przeglądarki, dostawcy usług certyfikacyjnych. Stowarzyszony z nim do pary klucz prywatny powinien być używany do podpisywania podzadania obliczeniowego kierowanego do komputera internauty od serwera W poprzez serwer S oraz ewentualnie do podpisywania komunikacji od serwerów W do serwerów S i także w niektórych sytuacjach serwerów reklamodawców. Należy podkreślić, że szczególnej ochrony wymaga klucz podpisujący stowarzyszony z publicznym, umieszczonym w kwalifikowanym certyfikacie.

    • Certyfikaty kluczy publicznych używane do podpisów i do zabezpieczania komunikacji w obrębie systemu Comcute, zarządzane przez własną infrastrukturę PKI. Klucz główny (root) może, ale nie musi, być podpisany z użyciem klucza prywatnego, którego do pary klucz publiczny jest certyfikowany przez kwalifikowanego dostawcę.

    12.8. Podsumowanie

    W rozdziale przedstawiono podstawowe mechanizmy niezbędne do zapewnienia bezpieczeństwa elementów składowych i całego systemu Comcute. Ze względu na powszechnie znane zagrożenia pochodzące z Internetu, najpierw powinna być opracowana polityka bezpieczeństwa, definiująca sposoby realizacji celów systemu i procedury postępowania w warunkach zagrożenia. O ile pewne elementy z poniższego zestawienia można pominąć w systemie laboratoryjnym, który jest izolowany od sieci zewnętrznej, to jednak w systemie docelowym niezbędne będzie zaprojektowanie i wprowadzenie następujących składników systemu bezpieczeństwa:

    • Polityka bezpieczeństwa – dokument zatwierdzony przez zarząd organizacji – właściciela systemu Comcute;
    • Infrastruktura klucza publicznego – hierarchiczna dla systemu i SPKI dla warstwy internetowej;
    • Mechanizmy i protokoły zapewniające poufność i wiarygodność komunikacji.

    12.9. Literatura

    1. Dokumenty NIST serii NCSC-TG, 1986-1991.
    2. COMCUTE – dokumentacja projektowa systemu laboratoryjnego, WETI PG 2010-2012.
    3. Menezes J., Oorschot P. C. van, Vanstone S. A.: Handbook of Applied Cryptography. (Kryptografia stosowana), WNT 2005.
    4. Schneier: Kryptografia dla praktyków, wyd.2, WNT 2000.
    5. Gollmann: Computer Security, 3rd. ed., J.Wiley&Sons 2011.
    6. Stokłosa J., Bilski T., Pankowski T.: Bezpieczeństwo danych w systemach informatycznych, PWN 2001.
    7. Nadalin, C. Kaler: OASIS Web Services Security: WS-Security Core Specification 1.1, http://www.oasis-open.org/committees/download.php/16790/wss-v1.1-spec-os-SOAPMessageSecurity.pdf, 2006
    8. Özsu M. T., Valduriez P.: Principles of Distributed Databases 3rd ed., Springer 2011
    9. Bosworth, S., Kabay, M.E. (ed.), Computer Security Handbook, 4th ed., J. Wiley&Sons, 2002
    10. Pieprzyk J., Hardjono T., Seberry J. – Teoria bezpieczeństwa systemów komputerowych, 2005, Helion.
    11. Szpryngier, P.: Infrastruktura klucza publicznego SPKI. W KASKBOOK. Technologie SaaS, red. H. Krawczyk, Gdańsk: Politechnika Gdańska 2004.

  • Rozpraszanie obliczeń za pomocą serwerów dystrybucyjnych

    W rozdziale omówiono zasady funkcjonowania serwerów dystrybucyjnych w systemie obliczeniowym klasy grid pracującym w trybie volunteer computing. Omówiono sposoby zwiększania wydajności tej warstwy systemu za pomocą zarządzania strumieniem paczek danych. Odniesiono się także do koncepcji map-reduce w implementacji przetwarzania równoległego.

    10.1. Paradygmat obliczeń za pomocą e-wolontariatu a korporacyjne obliczenia dedykowane w warunkach kryzysowych

    Systemy gridowe działające zgodnie z paradygmatem tzw. volunteer computing opierają się na serwerach dystrybucyjnych, które służą do interakcji z komputerami internautów. Dlatego też omówione zostaną warianty możliwych trybów pracy serwerów dystrybucyjnych w systemach gridowych. Ponieważ jednak rola tej klasy jednostek obliczeniowych zależy od paradygmatu obliczeń zespołowych internautów, warto omówić ich genezę i stan aktualny.

    Wolontariat obliczeniowy (ang. volunteer computing) jest rodzajem przetwarzania rozproszonego, w którym internauci i inni właściciele komputerów udostępniają bezpłatnie zasoby swoich komputerów (moc obliczeniową, zasoby dyskowe lub inne zasoby) w celu automatyzacji obliczeń jednego lub więcej projektów. Termin volunteer computing wprowadził Luis Sarmenta podczas programowania aplikacji w projekcie Bayanihan [8]. Alexandrov, Ibel, Schauser i Scheiman wdrożyli system prowadzenia volunteer computing jako SuperWeb, a obliczenia w takim systemie z wykorzystaniem języka Java – nazwali globalnymi (ang. Java-Based Global Computing) [1].

    Pierwszym projektem zrealizowanym w oparciu o paradygmat volunteer computing był Great Internet Mersenne Prime Search (GIMPS) w 1996 [7]. Liczby Mersenne’a (od nazwiska francuskiego matematyka Marina Mersenne’a) to liczby wyznaczane z zależności Mp=2p-1, gdzie p jest liczbą naturalną. Jeśli liczba Mersenne’a jest liczbą pierwszą, to wykładnik p jest także liczbą pierwszą, ale nie odwrotnie. Jeśli p jest liczbą pierwszą, to nie jest to warunek wystarczający, ale jedynie konieczny do tego, że liczba Mersenne’a Mp jest także liczbą pierwszą.

    Liczb pierwszych Mersenne’a jest 47, a największa z nich została wyznaczona dla p=43 112 609 przez Edsona Smitha 23 sierpnia 2008 roku w ramach projektu fridowego GIMPS. Największa liczba Mersenne’a składa się z 12 978 189 cyfr. Poszukiwaniem liczb pierwszych Mersenne’a i rozkładaniem liczb złożonych Mersene’a na czynniki pierwsze zajmują się badacze w projektach wykorzystujących e-wolontariat. Najbardziej efektywnym projektem jest właśnie GIMPS, w ramach którego odkryto dwanaście największych znanych liczb pierwszych Mersenne’a.

    W 1997 roku w ramach środowiska gridowego distributed.net rozpoczęto obliczenia związane z deszyfrowaniem zakodowanego tekstu za pomocą algorytmu RSA dla klucza 56-biotowego. Obecnie wiele pokrewnych zagadnień jest liczonych na tym gridzie. Kolejne projekty to Bayanihan, Popcorn i Charlotte [4]. W 1999 roku rozpoczęto obliczenia w ramach projektów SETI@home i Folding@home z udziałem setek tysięcy internautów, co było niespodziewanie pozytywnym efektem dla projektantów i wywołało falę medialnych dyskusji nad możliwościami technologii przetwarzania w Internecie.

    W 1998 także w komercyjnych projektach rozpoczęto wykorzystywanie e‑wolontariatu, co dotyczy szczególnie projektów Popular Power (poszukiwanie szczepionki przeciwko grypie), Porivo, Entropia (liczby Mersenne’a jeszcze raz, szczepionka przeciwko AIDS) i United Devices [8].

    W 2002 roku w projekcie Berkeley Open Infrastructure for Network Computing (BOINC) rozpoczęto realizację obliczeń, dostarczając oprogramowanie warstwy pośredniej dla volunteer computing, włączając w to oprogramowanie klienta, GUI, środowisko pracy aplikacji, oprogramowanie serwera i oprogramowanie strony projektu. Pierwszym zaawansowanym projektem na platformie BOINC był Predictor@home, który rozpoczęto w 2004 roku, a kolejnymi projektami: SETI@home i ClimatePrediction.net. Popularne projekty realizowane na tej platformie to Rosetta@home i Einstein@home[1].

    W 2007, społeczność World Community Grid (WCG) przeniosła swoje obliczenia z platformy the United Devices na BOINC. World Community Grid to platforma przetwarzania rozproszonego zarządzana przez IBM. W ramach WCG poszukuje się m.in. wielu potrzebnych szczepionek i leków przeciwko groźnym chorobom [7].

    W wyniku prac prowadzonych w ramach projektu Comcute, proponujemy wprowadzenie w warunkach kryzysowych paradygmatu instytucjonalnych obliczeń obowiązkowych (ang. obligatory computing). W proponowanym podejściu organizacje rządowe i samorządowe udostępniają zasoby komputerowe, inicjując linki do witryn sztabów antykryzysowych. Tej klasy obliczenia nazwaliśmy korporacyjnymi obliczeniami dedykowanymi w warunkach kryzysowych. Zasadność tego rodzaju obliczeń potwierdza poniżej opisana sytuacja kryzysowa w energetyce jądrowej.

    10.2.E-wolontariat w sytuacji awarii reaktora jądrowego

    W 2011 roku w czasie katastrofy elektrowni jądrowej Fukushima nastąpiła seria wypadków jądrowych w wyniku trzęsienia ziemi u wybrzeży Honsiu [3]. W rejonie katastrofy przestały działać superkomputery, na których prowadzono większość obliczeń wspierających działanie reaktorów, a także wspierających przewidywane akcje ratunkowe w wyniku wybuchu reaktorów. W tej sytuacji nie można było prowadzić obliczeń na dedykowanych superkomputerach i stacjach roboczych. Natomiast możliwy był dostęp do Internetu za pomocą komputerów internautów, a także komputerów znajdujących się w większości urzędów w pozostałej części Japonii. Wobec tego przeniesiono część oprogramowania antykryzysowego na ad-hoc zorganizowany grid i kontynuowano kluczowe obliczenia.

    Warto podkreślić, że podczas tej katastrofy jedną z awarii reaktora jądrowego oceniono najwyższym stopniem w siedmiostopniowej międzynarodowej skali INES [6]. W niektórych reaktorach doszło do stopienia rdzeni. Ponadto nastąpiła emisja substancji promieniotwórczych do środowiska, w tym przedostanie się do środowiska skażonej wody morskiej stosowanej do chłodzenia reaktorów. Prądy morskie do dnia dzisiejszego roznoszą skażenia po całym Pacyfiku. Szczególnie narażone są ryby, które znacznie dłużej przechowują skażenia promieniotwórczymi izotopami niż rośliny czy woda morska [3].

    W Niemczech z powodu obaw o bezpieczeństwo elektrowni jądrowych, kilka elektrowni jądrowych starszego typu zamknięto. Ocenia się, że z punktu widzenia intensywności emisji materiałów radioaktywnych katastrofa japońska nie była mniejsza niż katastrofa jądrowa w Czarnobylu. Natomiast ilość uwolnionego materiału promieniotwórczego była na poziomie ok. 10% tego, co zostało uwolnione w trakcie katastrofy w Czarnobylu [4].

    W sytuacji tego rodzaju katastrof niezbędne jest prowadzenie szybkiej i sprawnej akcji ratowniczej, co wiąże się z wykorzystaniem przygotowanego wcześniej odpowiedniego oprogramowania antykryzysowego. W wypadku awarii supercentrów komputerowych rozsądną alternatywą jest „przeniesienie” obliczeń na komputery internautów i pracowników administracji za pomocą systemu gridowego, np. Comcute JEE.

    10.3.Funkcjonowanie serwerów dystrybucyjnych realizujących paradygmat obliczeń za pomocą e-wolontariatu

    W systemie gridowym Comcute JEE (akronim CJEE) istotną rolę odgrywają serwery dystrybucyjne. Schemat funkcjonalny serwera dystrybucyjnego pokazano na rys. 10.1.

    Inicjacja zadania następuje po ściągnięciu na komputer internauty I strony webowej pobranej z portalu WWW stowarzyszonego z serwerem dystrybucyjnym S. Strona może zawierać banner reklamowy zawierający kod loadera, który wysyła żądanie zadania do serwera S.

    Żądanie zadania jest adresowane do modułu równoważącego obciążenia serwerów S, a następnie jest przekierowywane do najmniej obciążonego serwera S. Istnieje kilka metod równoważenia obciążenia (na różnych warstwach modelu sieci) [2]. W zaimplementowanym prototypie przyjęto, że równoważenie obciążeń między serwerami S odbywa się na wyróżnionym serwerze S.

    Schemat funkcjonalny serwera dystrybucyjnego
    Rys. 10.1. Schemat funkcjonalny serwera dystrybucyjnego

    Żądanie komputera internauty I jest przez serwer S kierowane do skojarzonego z nim węzła W. Jeśli węzeł W ma jakąś paczkę zadania do przetworzenia, to przesyła tę paczkę z powrotem przez serwer S do komputera internauty I. Paczka zadania zawiera: identyfikator zadania, kod obliczeń, identyfikator paczki danych oraz samą paczkę danych.

    Możliwy jest inny sposób inicjacji obliczeń polegający na bezpośrednim dołączeniu kodu obliczeniowego do kodu strony WWW. Kod inicjujący obliczenia rezydujący na komputerze internauty może także (w ramach przepisów prawa) przenieść się na komputer innego internauty i z tego nowego komputera zainicjować żądanie obliczeń do warstwy S. W szczególności możemy rozważać propagację kodu obliczeń podobną do „rozmnażania się” wirusów lub robaków internetowych. Oczywiście taki sposób propagacji obliczeń powinien być regulowany przepisami odnośnie przetwarzania w warunkach kryzysowych państwa.

    Po wykonaniu zadania komputer I zwraca wynik do serwera dystrybucyjnego wraz z identyfikatorem zadania oraz identyfikatorem paczki danych. Następnie komputer internauty I może otrzymać kolejną paczkę danych wejściowych, może też otrzymać nowy kod nowego zadania albo zakończyć pracę.

    10.4.Zwiększenie wydajności przesyłania zadań

    Można zwiększyć wydajność poprzez przesyłanie dwóch (lub więcej) paczek danych podczas pierwszego uruchomienia zadania na komputerze internauty. Wówczas komputer internauty po przetworzeniu pierwszej paczki danych i odesłaniu wyników realizowałby zadanie dla drugiej paczki czekając na kolejną porcję danych. To rozwiązanie nazywa się przeplotem komunikacyjnym [5].

    Innym sposobem zwiększenia wydajności jest przesłanie z węzła W do serwera S stosunkowo dużej ilości danych, np. stu paczek danych. Wówczas serwer S tworzy dla komputera internauty strumień danych wejściowych, a ten przetwarzając każdą paczkę danych zwraca do serwera S strumień wyników.

    Ze względu na zawodność obliczeń na komputerach internautów serwery w warstwie W mogą kopiować strumień danych dwukrotnie lub trzykrotnie, wysyłając kod obliczeń i dane do dwóch lub trzech grup rozłącznych serwerów S.

    10.5.Partycjonowanie danych i dystrybucja kodu obliczeń

    Zakładamy, że kod obliczeń jest definiowany i dostarczany przez zleceniodawcę obliczeń Z. w wybranej technologii programistycznej. Jest on przesyłany do komputera internauty I poprzez serwery W i S. Kod obliczeń nie ulega zmianom podczas dystrybucji.

    Podział danych i ich dystrybucja w warstwie W jest realizowana za pomocą algorytmu partycjonera. Z kolei scalanie wyników cząstkowych odbywa się również w warstwie W za pomocą algorytmu linkera. Trzeba podkreślić, że prawie każdy nowy kod zadania wymaga napisania nowego partycjonera i linkera paczek danych. Aby ograniczyć tę konieczność warto zdefiniować takie algorytmy partycjonera i linkera, które będą mogły być stosowane w różnych zadaniach, ale należących do tej samej klasy zadań.

    Załóżmy, że na podstawie jednego partycjonera następuje zrealizowanie zadania A klasy K, a także zadania B należącego do tej samej klasy K. Tak rozumiana uniwersalność partycjonera jest ograniczona do danej klasy zadań. Mamy zatem klasy rozwiązywanych problemów K1, K2, … , KK, które są zależne od partycjonera.

    Przykładowo, niech A będzie zadaniem polegającym na weryfikacji pewnego zbioru liczb naturalnych czy są pierwsze, a zadanie B weryfikuje hipotezę Collatza. Danymi wejściowymi w obu wypadkach jest zbiór liczb naturalnych ograniczony od góry pewnym elementem maksymalnym. Pracę obliczeniową (kod programu, dane wejściowe) dekomponujemy na mniejsze jednostki składające się z kodu programu i paczki danych, a następnie wysyłamy do komputerów internautów. Strumień paczek danych wejściowych generowany jest jednakowo dla obu prac obliczeniowych, tj. wyznaczanie liczb pierwszych i problem 3n+1. Każda paczka danych to para (a,b) opisująca przedział liczb naturalnych. Sekwencja kolejnych przedziałów właśnie generuje strumień, który partycjoner rozsyła do komputerów internautów.

    Serwer W dysponuje kodami obliczeniowymi wszystkich rozwiązywanych problemów i aktualizuje tabelę kodów obliczeniowych (identyfikator, zawartość kodu obliczeniowego) na podstawie zleceń z warstwy Z. Zleceniodawca obliczeń Z może dostarczyć kod rozwiązujący nową klasę problemu bądź też zrezygnować z prowadzenia obliczeń wybranej klasy. Może także dostarczyć kod jedynie na potrzeby jednorazowego uruchomienia.

    10.6.Zastosowanie koncepcji map-reduce do implementacji przetwarzania gridowego

    Koncepcja map-reduce to alternatywne podejście do przetwarzania strumienia danych. Paradygmat programowania rozproszonego map-reduce został zrealizowany w Google w 2004 roku, aby uczynić łatwiejszym pisanie aplikacji operujących na dużych ilościach danych. Ukrywa przed programistą większość problemów programowania współbieżnego. Wykorzystywany jest przez takie firmy jak Google, Yahoo, Amazon czy Facebook [9].

    Hadoop MapReduce to framework wspomagający pisanie aplikacji, które przetwarzają równolegle znacząceilości danych (rzędu terabajtów) za pomocą dużych klastrów (tysiące węzłów) w sposób niezawodny i odporny na uszkodzenia. Wszystkie dane nazywane są pracą, która zazwyczaj dzielona jest na niezależne paczki danych. Paczki są przetwarzane przez zadania klasy map w sposób całkowicie równoległy. Następnie sortowane są wyniki z zadań klasy map, które teraz stanowią dane wejściowe do zadań klasy reduce. Zazwyczaj zarówno dane wejściowe jak i wyjściowe z zadania są przechowywane w systemie plików. Framework zajmuje się szeregowaniem zadań, ich monitorowaniem i zapewnia ponowne wykonanie nieprawidłowo zakończonych zadań.

    Zazwyczaj węzły obliczeniowe i węzły przechowujące dane są takie same, gdyż framework MapReduce i Hadoop Distributed File System są uruchamiane uruchomione na tym samym zbiorze węzłów. Taka konfiguracja umożliwia skutecznie szeregowanie zadań w węzłach, gdzie dane są już dostępne, co skutkuje bardzo wysoką wydajnością.

    Framework MapReduce składa się z JobTrackera typu master i TaskTrackera typu slave w każdym węźle klastra. Master jest odpowiedzialny za szeregowanie zadań, ich monitorowanie i ponownie wykonanie nieprawidłowo zakończonych zadań. Slave realizuje zadania zgodnie z zaleceniami mastera.

    Aplikacje określają lokalizacje danych wejściowych i wyjściowych oraz wspierają funkcje map i reduce za pomocą implementacji odpowiednich interfejsów lub klas abstrakcyjnych. Te i inne parametry pracy stanowią konfigurację pracy. Klient zadania następnie przesyła pracę (plik JAR, wykonywalny itp.) oraz konfigurację do JobTrackera, który następnie przejmuje odpowiedzialność za dystrybucję oprogramowania/konfiguracji do slave-ów, szeregowanie zadań oraz ich monitorowanie, zapewniając status oraz informacje diagnostyczne do klienta pracy.

    Chociaż framework Hadoop jest realizowany w Javie, to aplikacje MapReduce nie muszą być napisane w Javie.

    • Hadoop Streaming to narzędzie, które pozwala użytkownikom na implementację i uruchamianie prac za pomocą wszelkich plików wykonywalnych (np. narzędzia powłoki) jak mapper lub reduktor.

    • Hadoop Pipes jest narzędziem klasy SWIG zgodnym z API C++do wdrożenia aplikacji w środowisku MapReduce (nie opiera się na Java Native Interface).

    MapReduce nie wykorzystuje Java Native Interface (JNI) macierzystego interfejsu programistycznego dla Javy. JNIumożliwia uruchamianie kodu w Javie wewnątrz wirtualnej maszyny Javy, we współpracy z aplikacjami i bibliotekami napisanymi w C, C++ czy asembler.

    Natomiast SWIG to narzędzie, które łączy programy napisane w C/C++ z różnymi językami wysokiego poziomu, w tym z językami skryptowymi Perl, PHP, Python, Tcl i Ruby. Ponadto możliwe jest łączenie z językami nieskryptowymi: C#, Common Lisp (CLISP, Allegro CL, CFFI, UFFI), D, Go, Java, Lua, Modula-3, OCAML, Octave i R. Także wspierane są różne interpretowane lub kompilowane implementacje klasy Scheme (Guile, MzScheme/Racket, Chicken). SWIG jest najczęściej wykorzystywany tworzenia środowisk do interpretowania lub kompilacji programów napisanych w językach wysokiego poziomu.

    SWIG umożliwia także implementację interfejsów użytkowników, a także może być wykorzystywany jako narzędzie do testowania i prototypowania aplikacji napisanych w języku C/C++. SWIG jest zazwyczaj stosowany do parsowania interfejsu C/C++ i generowania kodu w innym języku. SWIG może także eksportować parsowane drzewo w kod języka XML lub s-wyrażenia Lispa. SWIG jest oprogramowaniem bezpłatnym.

    Schemat przetwarzania sekwencyjnego w paradygmacie *map-reduce*
    Rys. 10.2. Schemat przetwarzania sekwencyjnego w paradygmacie *map-reduce*

    Zgodnie z koncepcją map-reduce(rys. 10.2) programista dostarcza implementacje dwóch funkcji: map oraz reduce:

    • Funkcja mappobiera fragment danych wejściowych i produkuje na ich podstawie ciąg par (klucz, wartość).

    • Funkcja reduceotrzymuje na wejściu wszystkie pary dzielące wspólny klucz, a następnie na ich podstawie generuje pary wyjściowe.

    Koncepcję tę łatwo zastosować do przetwarzania równoległego (rys. 10.3). Wówczas tworzy się wiele instancji funkcji map. Dane wejściowe są automatycznie dzielone na fragmenty, które są przesyłane do poszczególnych instancji funkcji map.

    Diagram przetwarzania równoległego w paradygmacie *map-reduce*
    Rys. 10.3. Diagram przetwarzania równoległego w paradygmacie *map-reduce*

    Koncepcja map-reduce jest w praktyce realizowana w warstwie W systemu Comcute JEE, przy czym funkcja map jest implementowana jako kod partycjonera, a funkcja reduce jako kod linkera.

    10.7.Komunikacja między S a warstwą W

    Poniżej zaprezentowano dwie koncepcje komunikacji między warstwą S i W. W wersji pierwszej internauta otrzymuje gotowy, zdefiniowany i ustalony kod programu realizujący określone operacje (funkcje) i kod ten jest niezmienny. Internauta pobiera natomiast dane parametryzujące wykonanie posiadanego kodu.

    W wersji drugiej internauta otrzymuje zarówno kod, jak i dane. W tej wersji zakłada się, iż na komputerze internauty (w serwerze w sensie architektury klient-serwer) realizowana będzie interpretacja (lub kompilacja) kodu w celu jego finalnego wykonania w lokalnym środowisku.

    Wariant pierwszy jest łatwiejszy w realizacji, natomiast w sposób istotny ogranicza zakres realizowanych zadań. W wersji tej zakłada się, iż do przeglądarki internauty dostarczane są gotowe fragmenty kodu w wersji finalnej (skompilowanej) w celu ich wykonania. W praktyce ogranicza to elastyczność systemu do z góry założonych i na wstępie opracowanych algorytmów bez możliwości ich dynamicznych modyfikacji. Inną zaletą takiego rozwiązania jest większa (niż w drugiej koncepcji) efektywna szybkość wykonywania założonych z góry zadań, które są przesyłane do komputerów internautów w stanie gotowości do uruchomienia.

    Wariant drugi zakłada dynamiczne dostarczanie zarówno kodu, jak i danych do przeglądarki internauty. Dynamiczne dostarczanie kodu do wykonania powoduje to, że system staje się w pełni otwarty i konfigurowalny dla pojawiających się zadań. W wariancie tym internauta otrzymuje do przeglądarki kod zadania wyrażony w pewnym języku programowania, musi ten kod zinterpretować (lub skompilować) i następnie go wykonać. Występuje tu konieczność rozbudowy środowiska uruchomieniowego u internauty. Wnosi to też pewien narzut czasowy na interpretację (lub kompilację) kodu, ale z drugiej strony nie zamyka zakresu wykonywanych zadań tylko do uprzednio określonego zdefiniowanego zbioru.

    W opracowaniu rozważane jest potencjalne wykorzystanie obu metod, ze zwróceniem uwagi na zalety oraz wady. Wariant pierwszy jest prostszy implementacyjnie oraz szybszy, wariant drugi natomiast jest elastyczny.

    10.7.1.Kooperacja między warstwą W a S przy statycznym zestawie zadań

    Schemat blokowy całości koncepcji w wariancie pierwszym przedstawiony został na rys. 10.4. Wyszczególnione zostały poszczególne elementy koncepcyjne oraz opisany został dynamiczny schemat komunikacji.

    W tej koncepcji budowy systemu zakładamy istnienie zamkniętej statycznej grupy zadań do realizacji. Kody zadań zostały wcześniej przygotowane, opracowane i zakodowane. Ich ciała wykonawcze (właściwe kody, bez danych) są dołączone do wtyczek służących do odtwarzania zawartości reklam. Całość operacji w ujęciu wykonawczym odbywa się następująco:

    • Dostarczenie i zapisanie kodów wykonawczych do właściwych wtyczek. (programów odtwarzających) Wtyczki powiązane są z określonymi reklamami i w przypadku pobierania określonej reklamy ładowana jest właściwa wtyczka z kodem wykonawczym.

    • Dane do określonego zadania przesyłane są z warstwy W do warstwy S i oczekują na pobranie w serwerze S.

    • Internauta łączy się poprzez przeglądarkę z serwerem publicznym P. Przeglądarka wysyła żądanie przesłania strony.

    • Serwer P przesyła zawartość strony WWW wraz z umieszczonym w niej linkiem do pobrania określonej reklamy.

    • Przeglądarka kontaktuje się z serwerem reklam, gdzie wysyła żądanie pobrania określonej reklamy.

    • Serwer reklam przesyła wymaganą reklamę, w określonym formacie. Przeglądarka po odebraniu reklamy potrzebuje określonej wtyczki do odtworzenia reklamy.

    • Przeglądarka wysyła żądanie pobrania określonego programu odtwarzającego. W ramach programu odtwarzającego (oprócz kodu do odtworzenia reklamy) znajduje się wcześniej zapisany kod zadania właściwego systemu Comcute.

    • Program odtwarzający jest pobierany. U internauty odtwarzana jest reklama, a jednocześnie wykonywany jest kod właściwy systemu Comcute.

    • Nawiązywane jest połączenie z serwerem S (przez wtyczkę). Wysyłana jest identyfikacja komputera internauty oraz identyfikator zadania, które będzie wykonane na komputerze internauty.

    • Serwer S wysyła dane dla tego zadania (o ile je posiada, jeżeli nie posiada to wysyła polecenie zakończenia). Serwer S może nie posiadać żadnych zadań do wykonania, gdyż mógł nie otrzymać żadnych zleceń od warstwy W.

    • Po wykonaniu zadania rezultaty są przesyłane do serwera S (wymagane jest podanie danych identyfikacyjnych, aby warstwa S mogła sklasyfikować otrzymane rezultaty).

    • Serwer S komunikuje się z warstwą W i wysyła rezultaty (wymagane jest podanie danych identyfikacyjnych zadania, aby warstwa W była w stanie określić jakiego zadania wyniki dotyczą).

    Schemat blokowy realizacji zadań w systemie Comcute – wariant 1.
    Rys. 10.4. Schemat blokowy realizacji zadań w systemie Comcute – wariant 1.

    Podstawowym wyzwaniem realizacyjnym w wariancie pierwszym jest głębokie osadzenie kodu zadań Comcute w programach odtwarzających treści reklamowe. Dla każdej poszczególnej reklamy wymagane jest opracowanie dedykowanego programu odtwarzającego, w którym zawarty jest określony kod zadania Comcute. Po pobraniu określonej reklamy konieczne jest pobranie dedykowanego dla niej odtwarzacza. Prowadzi to do konieczności realizacji serwera plug-in oraz utrzymywania go. Nie można wykorzystać tutaj standardowych rozwiązań. Zaletą jest natomiast niskie obciążenie internauty (przeglądarki). Dostaje jedynie gotowy kod do wykonania oraz dane do przetworzenia.

    10.7.2. Kooperacja między warstwą W a S przy dynamicznym zestawie zadań

    Schemat blokowy całości koncepcji w wariancie drugim przedstawiony został na rys. 10.5. Wyszczególnione zostały poszczególne elementy koncepcyjne oraz opisany został dynamiczny schemat komunikacji. Zwrócenia uwagi wymaga odmienny sposób przesłania kodu zadania do przeglądarki internauty.

    Schemat blokowy realizacji zadań w systemie Comcute – wariant 2.
    Rys. 10.5. Schemat blokowy realizacji zadań w systemie Comcute – wariant 2.

    W tej koncepcji budowy systemu zakładamy elastyczność w zakresie potencjalnych zadań do realizacji. Kody zadań mogą być zarówno brane z bazy algorytmów, które zostały wcześniej przygotowane, opracowane i zakodowane, ale również mogą być wprowadzane dynamicznie do systemu. Kody zadań do wykonania przesyłane są do realizacji w momencie potrzeby ich uruchomiania i nie są stałym elementem. Ich ciała wykonawcze (właściwe kody) wraz z danymi są przesyłane do interpretacji i wykonania w przeglądarkach. Całość operacyjna w ujęciu schematu blokowego odbywa się następująco:

    A. Dostarczenie i zapisanie pojedynczej wtyczki (programu odtwarzającego) Wtyczka jest jednakowa dla wszystkich reklam, jej zadaniem jest umożliwienie stworzenia środowiska dla wykonania kodu otrzymanego przez przeglądarkę internauty od warstwy S.

    B. Kod zadania wraz z danymi jest przesyłany z warstwy W do warstwy S i oczekuje na pobranie w serwerze S.

    C. Internauta łączy się poprzez przeglądarkę z serwerem P. Przeglądarka wysyła żądanie przesłania strony.

    1. Serwer P przesyła zawartość strony wraz z umieszczonym w niej linkiem do pobrania określonej reklamy.

    2. Przeglądarka kontaktuje się z serwerem reklam, gdzie wysyła żądanie pobrania określonej reklamy.

    3. Serwer reklam przesyła wymaganą reklamę. Przeglądarka po odebraniu reklamy potrzebuje wtyczki do odtworzenia reklamy. Przy czym rozważane jest wykorzystanie wtyczek standardowych (ewentualnie sparametryzowanych).

    4. Przeglądarka wysyła żądanie pobrania określonego programu odtwarzającego. W sytuacji, gdy pobierana jest jedna wersja wtyczki dla wszystkich reklam, operacja ta sprowadza się praktycznie do pojedynczego pobrania przez internautę.

    5. Program odtwarzający jest pobierany. U internauty odtwarzana jest reklama. W ramach wykonywania reklamy (w kodzie reklamy) realizowane jest właściwy kod Comcute. Zadaniem kodu jest nawiązanie połączenia z warstwą S (serwerem S) w celu pobrania kodu zadania Z wraz z właściwymi danymi.

    6. Nawiązywane jest połączenie z serwerem S (w trakcie wykonywania reklamy). Wysyłana jest identyfikacja komputera internauty wraz z informacją o gotowości przyjęcia zadania do wykonania).

    7. Serwer S wysyła kod posiadanego zadania Z wraz z danymi dla wykonania tego zadania (o ile je posiada, jeżeli nie posiada to wysyła polecenie zakończenia). Serwer S może nie posiadać żadnych zadań do wykonania, gdyż mógł nie otrzymać żadnych poleceń od warstwy W.

    8. W przeglądarce internauty odbierany jest kod wraz z danymi. Kod jest wykonywany. Po wykonaniu zadania rezultaty są przesyłane do serwera S (wymagane jest podanie danych identyfikacyjnych, aby warstwa S mogła sklasyfikować otrzymane rezultaty).

    9. Serwer S komunikuje się z warstwą W i wysyła rezultaty (wymagane jest podanie danych identyfikacyjnych zadania, aby warstwa W była w stanie określić jakiego zadania wyniki dotyczą).

    Podstawowym wyzwaniem realizacyjnym w wariancie drugim jest umożliwienie wykonania dynamicznie dostarczonego kodu do przeglądarki internauty. Należy spodziewać się, iż ten kod nie będzie mógł być w związku z tym zbyt obszerny. Ponadto należy stworzyć środowisko do wykonania tego kodu. W związku z tym, że środowisko to jest jednolite, rozważane jest wprowadzenie go do wtyczki (programu odtwarzającego), lub też wykorzystanie wtyczek standardowych, o ile posiadają zakładane możliwości wykonawcze. Niewątpliwą zaletą wariantu drugiego jest dynamiczna możliwość realizacji algorytmów. Ponadto algorytmy (zadania) są określane w warstwie W podczas pracy całości systemu Comcute, co umożliwia wyższy poziom kontroli funkcjonowania oraz dużą elastyczność operacyjną. Do rozwiązania pozostaje umieszczenie w treści reklam (serwer reklamowy) fragmentów kodu pozwalającego na skomunikowanie się z serwerem S w celu pobrania kodu zadania oraz danych dla jego wykonania.

    10.8. Podsumowanie

    Przyjęto, że serwer dystrybucyjny S może przydzielić kilka milionów zadań dziennie. Wymaga to efektywnego mechanizmu dostarczania zadań do komputerów internautów z równoważeniem obciążenia serwerów S. Istnieją dwie koncepcje dostarczania zadań: w postaci statycznego, gotowego do wykonania kodu zadania oraz w postaci kodu dynamicznie interpretowanego lub kompilowanego po stronie klienta w komputerze internauty.

    W sytuacji katastrof reaktorów jądrowych niezbędne jest prowadzenie szybkiej i sprawnej akcji ratowniczej, co wiąże się z wykorzystaniem przygotowanego wcześniej odpowiedniego oprogramowania antykryzysowego. Zazwyczaj oprogramowanie tej klasy wymaga zastosowania superkomputerów do prowadzenia obliczeń. Jednakże w wypadku awarii supercentrów komputerowych, tak jak to miało miejsce podczas katastrofy elektrowni jądrowej Fukushima, rozsądną alternatywą jest „przeniesienie” obliczeń na dziesiątki tysięcy komputerów instytucji rządowych za pomocą systemu gridowego Comcute JEE.

    10.9. Wykaz literatury

    1. Alexandrov A.D., Ibel M., Schause K.E., Scheiman K.E.: SuperWeb: Research issues in Java-Based Global Computing. Proceedings of the Workshop on Java for High performance Scientific and Engineering Computing Simulation and Modelling. New York: Syracuse University., 1996
    2. Bourke T.: Server Load Balancing, O’Reilly, Sebastopol, 2001
    3. Fukushima faced 14-metre tsunami. World Nuclear News. 24 March 2011. http://www.world-nuclear-news.org/RS_Fukushima_faced_14-metre_tsunami_2303113.html. March 2011.
    4. Karaul, M., Kedem, Z., Wyckoff, P. Charlotte: Metacomputing on the Web. Proceedings of the 9th International Conference on Parallel and Distributed Computing Systems, Sept 1996
    5. Kopparapu Ch.: Load Balancing Servers, Firewalls & Caches, Wiley, New York 2002
    6. Martin, Alex, “Lowdown on nuclear crisis and potential scenarios”, Japan Times, 20 March 2011, p. 3.
    7. Regev O., Nisan N.: The POPCORN market~Wan online market for computational resources. Proceedings of the First International Conference on Information and Computation Economies. Charleston, South Carolina, United States: ACM Press, New York, NY. pp. 148–157. October 25 – 28, 1998).
    8. Sarmenta L.F.G.: Bayanihan: Web-Based Volunteer Computing Using Java. Lecture Notes in Computer Science, 1368, Springer-Verlag, 1998. pp. 444-461. Proc. of the 2nd International Conference on World-Wide Computing and its Applications (WWCA’98), Tsukuba, Japan, March 3-4, 1998
    9. Syme M., Goldie P.: Optimizing Network Performance with Content Switching: Server, Firewall and Cache Load Balancing, Prentice Hall PTR, New York 2004

  • Architektura systemu Comcute

    W rozdziale przedstawiono architekturę systemu Comcute realizującego masywne przetwarzanie rozproszone wykorzystujące powszechny wolontariat użytkowników komputerów w sieciach rozległych.

    7.1. Wprowadzenie

    Założenia projektowe:

    1. System przetwarzania rozproszonego wykorzystujący powszechny wolontariat internautów musi zapewniać możliwość przetwarzania dużej ilości danych przy wykorzystaniu efektu skalowania obliczeń wykonywanych przez bardzo dużą liczbę komputerów.

    2. Dane przetwarzane przez system mogą mieć charakter zarówno w pełni jawny jak też poufny i tajny, należy więc dokonać takich decyzji projektowych, które z jednej strony maksymalnie uproszczą dołączanie mocy obliczeniowej internautów do systemu, a z drugiej strony zabezpieczą infrastrukturę systemu przed działaniami złośliwymi.

    3. Dane są dostarczane do internautów i przetwarzane przez nich w sposób jawny, przez zgłoszenie chęci uczestnictwa w projekcie obliczeniowym. Wyjątkiem może być ogłoszenie stanu kryzysowego i przejście w tryb przetwarzania wymuszonego.

    4. System jest systemem rozproszonym składającym się z wielu węzłów.

    5. System musi być odporny na ataki z zewnątrz, zarówno na przechwytywanie danych, ataki typu DoS, jak i celowe zniekształcanie wyników.

    6. System musi zapewnić możliwość kontynuowania obliczeń nawet wówczas, gdy większa część węzłów zostanie zaatakowana i wyeliminowana, w skrajnym wypadku aż do momentu, gdy jeden węzeł ma możliwość działania.

    7. Zleceniodawca (użytkownik zlecający obliczenia dla systemu) może zgłosić się do dowolnego węzła i odebrać wyniki z dowolnego innego węzła (działającego).

    8. Obliczenia mogą być czasochłonne – odstęp czasowy pomiędzy zleceniem obliczeń a odebraniem wyników może być długi, a moment odebrania wyników zależy od zleceniodawcy.

    9. System powinien zapewniać weryfikację wyników obliczeń np. przez porównanie rezultatów otrzymywanych od różnych internautów. Wyjątkiem są obliczenia, które mają charakter niedeterministyczny.

    10. Mogą istnieć sytuacje, w których zadanie obliczeniowe uznaje się za ukończone nawet wówczas, gdy wyniki nie zostaną policzone w 100%.

    7.2. Koncepcja architektury systemu

    System składa się z czterech warstw (rys. 7.1):

    • warstwy Z (zleceniodawcy), zapewniającej interfejs użytkownika dla użytkowników zlecających zadania obliczeniowe i separująca ich od warstwy wewnętrznej,

    • warstwy W (wewnętrznej), składającej się z serwerów W, odpowiedzialnej za podział (partycjonowanie) zadań obliczeniowych od zleceniodawcy Z na fragmenty, synchronizację i weryfikację wyników obliczeń (arbitraż) oraz ich scalanie i dostarczanie z powrotem do zleceniodawcy,

    • warstwy S (dystrybucyjnej, brzegowej), składającej się z serwerów S, zajmującej się dostarczaniem fragmentów zadań do obliczeń dla internautów i odbieraniem od nich wyników,

    • warstwy I (publicznej, zewnętrznej), w której komputery internautów I wykonują w tle właściwe obliczenia. Komputery internautów są dołączane się do systemu przez serwery publiczne P i stowarzyszone z nimi serwery przekierowujące R.

    Rys. 7.1. Koncepcja architektury systemu przetwarzania rozproszonego

    Oddzielenie warstwy dystrybucyjnej od warstwy wewnętrznej umożliwia:

    • dopasowanie liczby węzłów W do zadania obliczeniowego,
    • dopasowanie liczby węzłów S do liczby internautów i ich lokalizacji,
    • ochronę węzłów W dysponujących informacją o całym zadaniu (wraz z wynikami obliczeń) przed zagrożeniem z zewnątrz.

    Założenia projektowe systemu zakładają, że istnieje pełna kontrola nad budową i sposobem funkcjonowania węzłów W i serwerów S. Serwery R nie są projektowane w ramach systemu, lecz muszą być z nim „zaprzyjaźnione”, tzn. muszą mieć informacje o położeniu serwerów S i sposobie komunikacji z nimi. Nie ma żadnej kontroli nad serwerami P i komputerami internautów I.

    7.3. Współdziałanie komponentów

    Koncepcję współdziałania komponentów należących do różnych warstw ilustruje rys. 7.2.

    Koncepcja działania systemu Comcute - dystrybucja zadań
    Rys. 7.2. Koncepcja działania systemu Comcute: a) zlecanie i partycjonowanie zadań, b) dystrybucja zadań

    Działanie systemu składa się z pięciu faz:

    1. Faza zlecenia zadania:

      1. Zleceniodawca Z zleca zadanie obliczeniowe do dowolnego węzła warstwy W.

      2. Węzeł, który przyjmuje zadanie, rozsyła je do innych węzłów. Wszystkie węzły W dzielą zadanie na fragmenty wg tego samego deterministycznego algorytmu. Dzięki temu wszystkie węzły W mogą niezależnie oferować fragmenty zadania do wykonania dla internautów.

    2. Faza nawiązywania połączenia internautów z systemem:

      1. Internauta zgłaszający się do serwisu publicznego P żąda dostarczenia pewnej użytecznej treści.

      2. Serwis P łączy się z serwerem R w celu dołączenia dodatkowej treści (np. reklamy w technologii Flash) do treści żądanej przez internautę.

      3. Serwer R zgłasza się do „zaprzyjaźnionego” serwera S z żądaniem podania kodu rozszerzającego serwowaną treść o skrypt pełniący rolę loadera zadania obliczeniowego.

      4. Kod rozszerzenia zostaje dołączony do treści oferowanej przez R.

      5. Wzbogacona o kod rozszerzenia treść zostaje dostarczona do serwera P.

      6. Użyteczna treść wraz treścią dodatkową i kodem rozszerzenia zostaje dołączona do przeglądarki internauty.

    3. Faza dystrybucji zadań:

      1. Kod rozszerzenia (loadera) wykonuje się w ramach technologii oferowanych przez przeglądarkę internauty. Łączy się z serwerem S zgłaszając gotowość na przyjęcie zadania obliczeniowego.

      2. Serwer S przegląda dostępne serwery W w poszukiwaniu zadań do obliczenia.

      3. Zadanie składa się z fragmentów, z których pierwszy zawiera kod obliczeniowy i dane do obliczenia, a następne mogą zawierać tylko dane. Serwer S pobiera fragment zadania obliczeniowego z serwera W

      4. …i dostarcza zadanie do kodu rozszerzenia w przeglądarce internauty, gdzie to zadanie jest wykonywane.

    4. Faza zwracania wyników:
      1. Po obliczeniu fragmentu kod obliczeniowy zwraca wynik do węzła S,
      2. a ten zwraca je do tego węzła W, z którego pobrał fragment zadania do obliczenia.
    5. Faza kompletowania zadania:

      1. Węzły W luźno synchronizują stan fragmentów zadania. Ten sam fragment może (a czasami musi) być przydzielony do różnych internautów. Jeśli różne węzły otrzymują różne wyniki tych samych fragmentów, to muszą stosować algorytm arbitrażu dla ustalenia, który wynik jest prawidłowy.

      2. Wyniki po skompletowaniu są odsyłane do zleceniodawcy z dowolnego węzła W, który uczestniczył w obliczeniach.

    7.4. Sposoby dystrybucji zadań obliczeniowych

    Ponieważ system nie może w żaden sposób zagwarantować, że internauta nie zamknie przeglądarki lub nie przełączy się na inną stronę przed zakończeniem wykonywania swojego fragmentu zadania obliczeniowego, potencjalnie te same fragmenty zadań będą realizowane wielokrotnie przez węzły W aż do uzyskania odpowiedzi (od własnych internautów lub od innych węzłów). Taki mechanizm jest potrzebny do zapewnienia niezawodności systemu. Dla zapewnienia wiarygodności (uodpornienia na ataki podstawieniowe) obliczenia muszą być powtarzane (potencjalnie przez różne węzły), zaś wyniki porównywane ze sobą i wybierane przez głosowanie (min. 3 odpowiedzi). Węzły dystrybuują zadania wg algorytmu pseudolosowego. Jeśli algorytm wskazuje na zadanie, które ma już wyniki, to węzeł W prześle zadanie do realizacji wówczas, gdy ilość odpowiedzi jest mniejsza od minimalnej. Wszystkie wyniki są rejestrowane wraz z ilością „oddanych głosów”. Po skompletowaniu wszystkich wyników i scalaniu rozwiązania problemu wybierane są wyniki z największą ilością głosów (rys. 7.3).

    W problemach niedeterministycznych nie da sięzagwarantować wiarygodności tą metodą (wyniki obliczeń nie są znane z góry, a porównywanie ich nic nie da, bo odpowiedzi mogą być różne). Dlatego ze względu na koszt czasowy obliczeń, jeśli algorytm wyboru zadania przez węzeł W wskaże zadanie, które ma już odpowiedź, to węzeł pominie to zadanie. Nie da się w całości wyeliminować powtórzeń tą metodą, ale ilość powtórzeń będzie minimalna (algorytm pseudolosowy będzie powodował inicjowanie różnych zadań w tym samym czasie a algorytm synchronizacji daje duże prawdopodobieństwo, że to samo zadanie nie zostanie ponownie zainicjowane).

    Założeniem jest dystrybuowanie zadań do internautów w sposób jawny, ale mało inwazyjny w normalne korzystanie z serwisów internetowych. Internauci zgłaszając się do serwerów publicznych pobierają z nich treści interesujące dla siebie (np. serwisy wiadomości, aplikacje do komunikacji peer-to-peer, aplikacje gier internetowych, muzyka, zdjęcia i filmy), a wraz z tymi treściami pobierają zadania obliczeniowe do wykonania.

    Treści pobierane przez internautów można podzielić nanastępujące kategorie:

    1. statyczne strony HTML – praktycznie bardzo krótko goszczą internautów, którzy po ewentualnym zapoznaniu się z treścią przechodzą do kolejnej strony,

    2. dynamiczne strony HTML – tworzone dynamicznie po stronie serwera w oparciu np. o technologie JSP, ASP, AJAX; dominują we współczesnych serwisach typu serwis wiadomości, serwis pogodowy, rozkład jazdy, rezerwacja biletów; są już ciekawsze dla internautów, jednak ich czas przebywania na takiej stronie jest ograniczony do kilku minut,

    3. reklamy, bannery reklamowe w technologii Flash – stanowią często treści niepożądane z punktu widzenia internauty; jeśli są wkomponowane w treść strony, to jeszcze są tolerowane; jeśli zasłaniają właściwą treść strony, to są najczęściej jak najszybciej zamykane lub blokowane a priori,

    4. zdjęcia, muzyka, filmy – ściągane przez programy typu peer-to-peer do odtworzenia na wbudowanej w system klienta przeglądarce multimedialnej lub z wyspecjalizowanych serwisów do odtwarzania na bieżąco w multimedialnej wtyczce do przeglądarki internetowej; na tych stronach internauci przebywają przez dość długi czas, a jeśli słuchają muzyki i oglądają filmy, to nawet kilkadziesiąt minut bez przerwy,

    5. gry internetowe – są aplikacjami najczęściej graficznymi działającymi po stronie klienta (np. w technologii Java), sieć jest wykorzystywana do komunikowania się między graczami (np. w grach zespołowych); internauci potrafią spędzać na takich stronach nawet wiele godzin,

    6. wiadomości od innych internautów – w formie wiadomości pocztowych (email) lub komunikatów przesyłanych na bieżąco przez specjalne komunikatory (typu Gadu-Gadu) wbudowane w przeglądarkę lub zainstalowane osobno w systemie; forma komunikatorów jest często sprzężona z 4. i 5. kategorią treści. W niektórych przypadkach tego typu aplikacje działają praktycznie bez przerwy,

    7. aplikacje usługowe działające po stronie klienta – oparte o najnowsze technologie Flex i Silverlight; jeśli internauci potrzebują usług wymagających względnie dużej mocy obliczeniowej lub działających na względnie dużych danych, to zamiast wysyłać dane do obróbki po stronie serwera pobierają aplikację działającą po stronie klienta i w ten sposób rozproszony system wykorzystuje rozproszoną moc obliczeniową; internauci spędzają na tych stronach tyle czasu, ile potrzebują do wykonania usługi.

    Z punktu widzenia celu systemu interesujące są te kategorie treści, które spełniają łącznie następujące warunki:

    1. po stronie klienta jest uruchamiany kod wykonywalny w pewnym języku skryptowym,

    2. umożliwiają w sposób nieinwazyjny uruchomienie procedur skryptowych, których wykonanie nie będzie powodowało istotnego spadku wydajności ani pogorszenia funkcjonalności zasadniczego kodu klienta,

    3. angażują czas procesora klienta na tyle dużo, aby użytkownik nie odczuł wykonania zadania obliczeniowego w tle, ale jednocześnie na tyle mało, aby zadanie obliczeniowe mogło zostać wykonane,

    4. angażują czas internautów na tyle długo, aby procedura skryptowa zdążyła wykonać dane zadanie i odesłać wyniki na serwer zanim internauta przełączy się na inną stronę,

    5. umożliwiają dynamiczne dopasowanie się do zmieniających się zadań obliczeniowych po stronie serwera.

    Stąd wynika, że w dalszych pracach trzeba skoncentrować się na treściach z kategorii 4 – 7. Wszystkie one działają w oparciu o aplikacje pracujące po stronie klienta i w taką aplikację muszą być wbudowane moduły obliczeniowe (wymaga to uzgodnienia między organizacją zarządzającą systemem obliczeniowym a kadrą zarządzającą serwerami R i jej administratorami).

    Nie znaczy to, że należy całkowicie pominąć pierwsze trzy kategorie treści. Chociaż czas przebywania internauty na stronach HTML statycznych i dynamicznych (z kategorii 1 i 2) jest dość krótki, to zysk ze stosowania systemu przetwarzania wolontariatowego wynika ze skali obliczeń – bardzo dużej ilości często krótkich, podstawowych obliczeń. Dlatego również wykorzystanie statycznych i dynamicznych strony może być opłacalne. Jeśli są one zaopatrzone w bannery reklamowe Flash (kategoria 3), to można treść bannera wzbogacić o komendy ActionScript tworząc w ten sposób miniaplikację działającą po stronie klienta.

    Elastyczne dopasowywanie się systemu do zmiennychzadań obliczeniowych trzeba zapewnić przez dołączanie zmieniających się modułów obliczeniowych do użytecznej treści WWW. Ważne jest, aby treść WWW udostępniana przez serwery P odwoływała się do serwerów R, które będą wzbogacały ją o kod rozszerzający pełniący funkcję loadera, który będzie pobierał z serwera W poprzez serwer S moduł obliczeniowy zawierający kod i dane do obliczenia Możliwe jest też inne rozwiązanie. Można do internauty dostarczyć gotowy kod obliczeniowy, który będzie pobierał jedynie dane. To rozwiązanie jest mniej elastyczne, ale nie wymaga tworzenia specjalnego środowiska uruchomieniowego po stronie internauty.

    Tryb pracy w sytuacji szczególnego zagrożenia

    W sytuacji szczególnego zagrożenia założenie o dobrowolnym uczestnictwie w dystrybucji i przetwarzaniu zadań staje się nieaktualne. Internauci świadomi zagrożenia instytucji państwowych mogą zdecydować się na udział w obliczeniach z pobudek patriotycznych, ale również odpowiednie przepisy prawne mogą usankcjonować narzucenie wykorzystywania ich mocy obliczeniowej. Wówczas serwisy S mogą zaoferować specjalną aplikację, która będzie jawnie wykonywać zadania obliczeniowe po stronie klienta na komputerach internautów, co pozwoli na pominięcie mechanizmu doklejania dodatkowego kodu do treści oferowanych przez serwery P.

    Komercyjny tryb pracy

    W zastosowaniach komercyjnych można zastosować obliczenia jawne i zwiększyć obciążenie komputerów internautów. Można też zwiększyć zaufanie do aplikacji i w ten sposób częściowo zapewnić możliwość obliczeń peer-to-peer (do pewnego stopnia, bo ograniczenia są przez zapory sieciowe).

    Sekwencja dystrybucji zadania dla wyspecjalizowanego kodu obliczeniowego
    Rys. 7.3. Sekwencja dystrybucji zadania: a) dla uniwersalnego kodu rozszerzającego, b) dla wyspecjalizowanego kodu obliczeniowego

    7.5. Literatura

    1. Kuchta Jarosław, Matuszek Mariusz, Czarnul Paweł, Szpryngier Piotr: Projektarchitektury środowiska laboratoryjnego systemu Comcute – 2011, Raport techniczny WETI nr 32/2011
    2. Use-It-Better: Analiza możliwości rekrutacji mocy obliczeniowej w Internecie. dokument wewnętrzny opracowany w ramach projektu Comcute, 2011
    3. Couloris G., Dollimore J., Kindberg T.: Distributed Systems: Concepts and Design. Addison Wesley Longman Ltd., London, 1994

  • Bezpieczeństwo transferu zestrukturalizowanych plików XML w sieci grid w oparciu o usługi Web Service poprzez protokół SOAP

    Niezależny protokół SOAP (ang. Simple Object Access Protocol) działający głównie ponad protokołem HTTP (inne protokoły transportowe to np. MSMQ, MQ Series, SMTP lub TCP/IP) posiada na dzień dzisiejszy wiele rozwiązań dotyczących bezpieczeństwa transferu zestrukturalizowanych plików XML (ang. Extensible Markup Language).W rozdziale zaprezentowano sposoby zapobiegania nieautoryzowanym dostępom do danych przesyłanych w sieci grid przy pomocy rozproszonych komponentów udostępniających usługi Web Service poprzez protokół SOAP.

    6.1. Wstęp

    Architektura środowiska grid zdefiniowano w standardach OGSA (ang. Open Grid Services Architecture), OGSI (ang. Open Grid System Infrastructure) oraz WSRF (ang. Web Services Resource Framework). Standardy te określają wymagania dla interfejsu sieciowego i sposób budowania oprogramowania dla środowiska z wykorzystaniem usług sieciowych.

    Grid to infrastruktura sprzętowa i programowa, która w sposób niezawodny, spójny i rozproszony zapewnia dostęp do potężnych zasobów obliczeniowych. Składa się z wielu heterogenicznych węzłów, zapewnia ściśle kontrolowane współdzielenie zasobów, integruje i steruje użytkownikami. W dużej mierze większość systemów Grid opiera się na idei Web Services. Systemy tej klasy są przezroczyste, natychmiastowo dostępne oraz osiągają wydajność porównywalną z superkomputerami przy niskim koszcie budowy.

    Wysoki stopień różnorodności wykorzystywanych komponentów doprowadził do przyjęcia klepsydrowego modelu architektury systemów gridowych (patrz rys. 6.1). Paradygmat SOA (ang. Service-Oriented Architecture) nie pozostał bez wpływu na architekturę grid. OGSA (ang. Open Grid Service Architecture) stworzone przez OGF (ang. Grid Forum) to standard opisujący architekturę grid w oparciu właśnie o ten paradygmat (rys. 6.2) [40,43,58,59].

    Klepsydrowy model architektury systemów grid
    Rys. 6.1. Klepsydrowy model architektury systemów grid
    Standardy architektury grid oparte na paradygmacie SOA
    Rys. 6.2. Standardy architektury grid oparte na paradygmacie SOA [60]

    Web Services to technologia konstrukcji rozproszonych komponentów usługowych, stanowiących podstawę dla realizacji aplikacji biznesowych w architekturze zorientowanej na usługi. Zgodnie z powszechnie akceptowaną definicją, usługa Web Service to zwarty, samodokumentujący się komponent programowy, który może być przez swojego twórcę zarejestrowany w sieci komputerowej, a następnie przez twórcę aplikacji-konsumenta odkryty i wywołany w trybie zdalnego wykonania. Technologia Web Services opiera się na szeregu skorelowanych rozwiązań informatycznych, spośród których najważniejsze to:

    • protokół komunikacyjny SOAP – służący do przekazywania zdalnych wywołań
    • język opisu interfejsu usługi WSDL – służący do dystrybucji parametrów połączeń sieciowych
    • specyfikacja bazy danych UDDI – służącej do rejestracji udostępnianych komponentów usługowych.

    Powstało wiele specyfikacji WS-* (organizacja OASIS) składające się na architekturę GXA (ang. Global XML Web Service Architecture), które rozbudowują SOAP o dodatkowe funkcje zabezpieczeń dla usług Web Service:

    • WS-Security
    • WS-SecureConversation
    • WS-Policy
    • WS-SecurityPolicy
    • WS-Trust
    • WS-Authorization
    • WS-Federation
    • WS-Federation Active Requestor Profile
    • WS-Federation Passive Requestor Profile [1-9,11,22,23]

    6.2. Podstawowe metody uwierzytelniania

    Metoda uwierzytelniania jest zdefiniowana w RFC-2617. Jest używana w tzw. Basic oraz Digest Authentication i opisana w specyfikacji HTTP. Zakłada istnienie dwóch elementów: nazwy użytkownika oraz hasła. Hasło może być przesyłane otwartym tekstem, ale może być również zakodowane w oparciu o mechanizm wykorzystywany w HTTP Digest Authentication, np. metodą Base64. Serwer WWW, z którym następuje połączenie, posiada listę kontroli dostępu, która pozwala również na przeprowadzenie autoryzacji. Mechanizm ten, nie jest wystarczająco bezpieczny, gdyż bardzo łatwo jest podsłuchać nazwę użytkownika i hasło.

    Aby tego uniknąć stosuje się protokół SSL/TLS (zdefiniowany w RFC-2246). W protokole tym podczas nawiązywania połączenia dochodzi do wymiany certyfikatów i kluczy publicznych serwera i użytkownika oraz do uzgodnienia symetrycznego klucza, który jest następnie wykorzystywany do szyfrowania przesyłanych danych. Protokół SSL/TLS zapewnia uwierzytelnianie zarówno klienta jak i użytkownika (poprzez weryfikację certyfikatów), poufność (dzięki szyfrowaniu) oraz integralność (razem z danymi jest przesyłany również ich skrót). Nie zapewnia on jednak niezaprzeczalności, ponieważ zarówno serwer jak i użytkownik stosują ten sam klucz. W protokole SSL nie jest obowiązkowe przesyłanie certyfikatu i klucza publicznego przez użytkownika przez co nie jest zapewnione również uwierzytelnianie klienta.

    Specyfika protokołu SOAP pozwala na to, że w komunikacji pomiędzy dwiema organizacjami mogą pojawiać się pośrednicy, a u każdego z nich może zajść potrzeba zatajenia części wiadomości. Niestety, protokół SSL szyfruje cały komunikat, a dodatkowo, jako protokół warstwy transportowej, zapewnia komunikację jedynie pomiędzy dwoma węzłami, przez co umożliwia pośrednikom odczytanie całego komunikatu.

    Innym sposobem uwierzytelnienia jest umieszczenie w nagłówku SOAP certyfikatu X.509, który pełni rolę żetonu zabezpieczeń identyfikującego klienta, lub osobę w imieniu której działa aplikacja kliencka. Certyfikat X.509 może być zmapowany na konkretnego użytkownika aplikacji umożliwiając tym samym określenie jego uprawnień w ramach usługi. Certyfikat X.509 jest wówczas umieszczany jako zawartość elementu BinarySecurityToken i kodowany w Base64.

    Zgodnie ze specyfikacją WS-Security BinarySecurityToken może tak naprawdę przenosić w sobie 3 możliwe ładunki (ang. payloads):

    • wsse:X509v3 – informuje, że binarnym żetonem jest certyfikat X.509 w wersji 3
    • wsse:Kerberos5TGT – żetonem jest Ticket Granting Ticket protokołu Kerberos
    • wsse:Kerberos5ST – Service Ticket protokołu Kerberos

    Korzystanie z protokołu Kerberos wymaga od użytkownika podania dowodu potwierdzającego tożsamość czyli tzw. credentials, np. pary <nazwa użytkownika>/<hasło>, bądź certyfikatu X.509. Jeśli uwierzytelnienie przebiegnie pomyślnie klient otrzyma tzw. Ticket Granting Ticket (akronim TGT). Klient nie może odczytać TGT, ale może za to wykorzystać ten bilet do otrzymania tzw. Service Ticket (akronim ST) od Ticket Granting Service (akronim TGS). TGS jest usługą odpowiedzialną za przyznawanie biletów upoważniających do korzystania z konkretnych usług. Po otrzymaniu ST, klient może korzystać z danej usługi dla której przyznano mu ST.

    Każda z wymienionych metod uwierzytelnienia wykorzystuje mechanizmy kryptograficzne umożliwiające podpisanie całego komunikatu, bądź wybranych fragmentów. W przypadku certyfikatu X.509 jest towarzyszący zawartemu w certyfikacie kluczowi publicznemu, klucz prywatny. W przypadku Kerberos jest to klucz sesyjny zawarty w biletach (TGT lub ST). W przypadku <nazwa użytkownika>/<hasło> jest to PBE (ang. Based Encryption) [9,10,12,13,14].

    6.3. WS-Security, XMLDS i XMLENC

    Standardy XMLDS (XML Digital Signature) i XMLENC (XML Encryption) to standardy ogólne, nie związane bezpośrednio z Web Services. Sposób ich wykorzystania do szyfrowania plików XML poprzez SOAP zdefiniowano w specyfikacji WS-Security.

    Specyfikacja WS-Security nie opisuje jednego protokołu wymiany komunikatów poprzez SOAP, ale stanowi szkielet, na bazie którego można budować własne protokoły bezpieczeństwa. Umożliwia wykorzystanie dowolnych algorytmów podpisu elektronicznego i szyfrowania w celu zapewnienia uwierzytelniania, integralności, poufności i niezaprzeczalności przesyłanych komunikatów. Definiuje w nagłówku komunikatu SOAP łańcuch kolejnych transformacji i podpisów, którym podlegają fragmenty, bądź całość komunikatu, w celu zapewnienia różnych poziomów poufności, pozwalając pośrednikom na dostęp jedynie do fragmentów komunikatu przeznaczonych dla nich.

    Specyfikacja XLMENC pozwala na zdefiniowanie plików XML zawierających dane zaszyfrowane dowolnym algorytmem kryptograficznym, zarówno symetrycznym (gdzie do zaszyfrowania i odszyfrowania używa się tego samego klucza) jak i asymetrycznym (gdzie używa się dwóch kluczy: publiczny do szyfrowania i prywatny do odszyfrowania wiadomości). W jednym pliku XML można również umieścić fragmenty zaszyfrowane różnymi algorytmami. Dzięki standardowi XMLENC możliwe jest konstruowanie komunikatów SOAP, w których poszczególne fragmenty mają różny poziom poufności, przykładowo część danych może zostać odczytana jedynie przez pośredników, a część jedynie przez adresata.

    Specyfikacja XLMDS pozwala na zastosowanie podpisu elektronicznego do podpisywania komunikatu SOAP wywołującego usługę. Można użyć różnych algorytmów kryptografii symetrycznej jak i asymetrycznej do wygenerowania i uwierzytelnienia podpisu elektronicznego. Przy zastosowaniu kryptografii symetrycznej jest możliwość wygenerowania tzw. certyfikatu, czyli elektronicznego dokumentu, który wiąże tożsamość organizacji z jej kluczem publicznym. Dokument ten jest podpisany cyfrowo przez zaufanego administratora certyfikatów [17,19,31,32,46,27].

    6.4. WS-SecureConversation

    WS-SecureConversation jest to rozszerzenie WS-Security definiuje jednokrotne wzajemne uwierzytelnienie obu stron, oraz ustalenie wspólnego klucza np. symetrycznego algorytmu szyfrowania komunikacji, który będzie wykorzystywany do szyfrowania wymiany wszystkich kolejnych komunikatów SOAP aż do wygaśnięcia sesji [35].

    Kryptografia klucza publicznego zapewnia bardzo wysoki poziom zabezpieczenia pod względem poufności, czy niezaprzeczalności jednak jest bardzo kosztowna pod względem przetwarzania. Dlatego w praktyce kryptografia klucza publicznego jest stosowana do szyfrowania bardzo niewielkich partii danych (do kilkudziesięciu bajtów). Pod względem wydajności szyfrowanie symetryczne przewyższa szyfrowanie asymetryczne. Z drugiej strony szyfrowanie symetryczne wymaga by po obydwu stronach znajdował się ten sam współdzielony klucz tajny.

    W praktyce najczęściej stosuje się rozwiązanie hybrydowe łączące zalety obydwu rodzajów szyfrowania. Specyfikacja takiego rozwiązania została umieszczona właśnie w WS-SecureConversation.

    Specyfikacja definiuje zabezpieczenie sesji składających się z więcej niż pojedynczego komunikatu. Definiuje także kontekst bezpieczeństwa (ang. security context) ustalany pomiędzy obydwoma stronami konwersacji. Kontekst bezpieczeństwa jest oparty o współdzielone klucze tajne (ang. shared secrets). Kontekst jest współdzielony przez strony konwersacji na czas trwania sesji. Na podstawie shared secrets generowane są sesyjne klucze tajne używane do zabezpieczania poszczególnych komunikatów.

    WS-SecureConversation definiuje 3 możliwe sposoby ustalenia kontekstu bezpieczeństwa:

    • ustalenie współdzielonego klucza tajnego (shared secret) przez zaufaną trzecią stronę – security token service. W takim przypadku strona inicjująca połączenie pobiera shared secret (żeton) i przekazuje go drugiemu uczestnikowi komunikacji.

    • ustalenie shared secret oraz kontekstu bezpieczeństwa przez jedną ze stron komunikacji i przekazanie go stronie przeciwnej.

    • negocjacja klient i usługa (znana z SSL/TLS) ustalają sposób najwłaściwszy dla obydwu stron sposób zabezpieczenia.

    Czas życia kontekstu bezpieczeństwa nie zawsze pokrywa się z czasem istnienia sesji – kontekst może mieć ustalony czas ważności. Żeton kontekstu bezpieczeństwa zawiera współdzielony klucz tajny, który stanowi podstawę do generowania kluczy służących do podpisywania i szyfrowania komunikatów. Szyfrowanie każdego komunikatu odbywa się innym kluczem tajnym, który jest tworzony na podstawie klucza dotychczasowego oraz przetworzonych danych. Ten rodzaj zabezpieczenia ma zastosowanie, gdy komunikacja między klientem a usługą nie sprowadza się do jednego komunikatu – w przeciwnym razie należy się zastanowić, czy narzut związany z negocjacją klucza będzie w ogóle opłacalny wydajnościowo [17,19,31,32,46,27].

    6.5. WS-Policy

    Częścią metadanych opisujących interfejs (format komunikatów opisany w WSDL) mogą być również dodatkowe informacje prezentowane przez WS, które bezpośrednio nie dotyczą funkcjonalności, a wymagań WS w stosunku do klienta – jest to tzw. polityka usługi. Zadaniem tej specyfikacji jest zapewnienie szkieletu, który można wykorzystać do komunikowania przez usługę Web Services twierdzeń dotyczących jej cech i wymagań, takich jak na przykład: wymagane kodowanie przesyłanych komunikatów lub obsługiwane algorytmy podpisu elektronicznego. WS-Policy jest szkieletem, natomiast to jakie cechy usługi można komunikować definiują osobne specyfikacje zależne od domeny zastosowań.

    Zgodnie z WSDL komunikaty SOAP są grupowane w operacje, które opisują podstawowe wzorce wymiany komunikatów (request/response). Z kolei operacje są grupowane w interfejsy – czyli zgodnie ze specyfikacją WSDL tzw. porty. Na końcu porty są wiązane z konkretnym transportem HTTP, TCP, czy SMTP. WSDL stanowi podstawę dla określenia interfejsu usługi, z której korzystają narzędzia programistyczne. Niestety opis WSDL nie jest wystarczający by ująć wszystkie możliwe cechy usługi – przykładowo informację o dostępności usługi (w określonych godzinach, czy dniach), informacje dotyczące uprawnień do korzystania z usługi (kto jest uprawniony, a kto nie jest uprawniony), zabezpieczenie komunikacji. Tego rodzaju informacje musiały być do tej pory przekazywane w sposób niezależny od samych metadanych WS i tym właśnie aspektom jest poświęcona specyfikacja WS-Policy.

    Podstawą opisu każdej polityki jest tzw. asercja polityki (ang. policy assertion). Asercja umożliwia odpowiednie rozszerzenie metadanych w trakcie rozwoju usługi, jak również podczas, lub po wdrożeniu. Najprostszymi przykładami ograniczeń narzucanych przez asercje mogą być:

    • maksymalny rozmiar komunikatu (co może mieć znaczenie np. dla urządzeń przenośnych, albo ze względów wydajnościowych)
    • okresy dostępności usługi

    Poszczególne asercje mogą być grupowane w alternatywy, które są wspierane przez klienta o ile spełnia on wszystkie wymagania przedstawione w alternatywie. Wsparcie alternatywy oznacza, że podmiot żądający (ang. requestor) spełnia wszystkie asercje wymienione w ramach tej alternatywy – co jest ustalane automatycznie poprzez ustalanie wyników poszczególnych asercji składających się na alternatywę. Cała polityka jest wspierana przez klienta o ile spełnia on warunki wymienione w przynajmniej jednej alternatywie tej polityki [16,47,48].

    6.6. WS-SecurityPolicy

    Jest to specyfikacja rozszerzająca WS-Policy, która definiuje twierdzenia związane z wymaganiami dotyczącymi zabezpieczenia komunikacji z daną usługą Web Service. Wprowadza ona dodatkowe asercje:

    • żetony bezpieczeństwa
    • integralność, poufność i czas życia komunikatów
    • widoczność zawartości komunikatów dla pośredników
    • ograniczenia dotyczące nagłówka bezpieczeństwa[16,47,48]

    6.7. WS-Trust

    Usługa może zażądać od klienta spełnienia pewnych warunków opisanych w polityce: nazwy użytkownika, klucza, uprawnień, itp. Jeśli klient nie dostarczy takich dowodów (claims) w komunikacie może spróbować odwołać się do odpowiedniej zaufanej trzeciej strony (authority), które mogłoby dostarczyć mu odpowiednie żetony bezpieczeństwa stanowiące dowód jego uprawnień do usługi. Model bezpieczeństwa definiowany przez WS-Trust opiera się na tym, że każda usługa Web Service może wymagać, aby przychodzące żądanie zawierało podpisany żeton bezpieczeństwa.

    WS-Trust jest rozszerzeniem WS-Security i obejmuje operacje dotyczące żetonów bezpieczeństwa:

    • żądanie
    • przyjmowanie
    • wystawianie
    • odnawianie
    • walidację

    Zaufana trzecia strona (ang. security token service) może być wskazana w polityce usługi. Security token service jest odpowiednikiem Key Distribution Center znanego z Kerberos. Zaufana trzecia strona może ze swojej strony również zażądać dowodów (ang. claims), że dany klient jest rzeczywiście uprawniony do wystawienia mu certyfikatu.

    WS-Trust opisuje również protokół challenge-response wykorzystywany w momencie pobierania żetonu przez klienta (bądź któregoś z pośredników) – strona ubiegająca się o żeton musi w jakiś sposób udowodnić, że jest do tego uprawniona, że może być jego właścicielem. Jeśli klient, bądź jeden z pośredników dostarczy żądanych dowodów sama usługa weryfikuje, czy ufa danemu security token service w zakresie wystawiania żetonów danego typu. Usługa może również próbować zweryfikować dostarczone żetony u samego wystawcy (security token service). [33,34]

    6.8. WS-Authorization, WS-Federation

    Główne zadania zdefiniowane w WS-Authorization:

    • uwierzytelnianie – określenie tożsamości osoby lub obiektu
    • autoryzacja – określenie praw dostępu do danych, metod lub obiektów
    • integralność – sprawdzenie czy dane nie zostały zmienione w drodze do celu
    • podpis – sprawdzenie źródła danych
    • poufność – limit użytkowników z prawami dostępu
    • polityka prywatności – sprawdzanie nadużyć zasobów

    WS-Federation definiuje mechanizmy tłumaczenia odrębnych rodzajów zabezpieczeń na zgodne z wywołującym je klientem [44,61].

    6.9. Podsumowanie

    Bezpieczeństwo aplikacji zależy nie tylko od zastosowanych w niej standardów, ale również od projektu samej aplikacji. Nawet najlepiej implementujące standardy usługi Web Services mogą być podatne na ataki typu SQL Injection lub wiele innych sposobów włamań. Niebezpieczeństwo z tej strony można zminimalizować jedynie starannie projektując usługi i przeprowadzając długie testy.

    Aktualne mechanizmy (rys. 6.3) pozwalają na stworzenie dobrze zabezpieczonego środowiska grid opartego na powiązanych ze sobą usługach i aplikacjach, gdzie zaciera się różnica między aplikacjami okienkowymi a aplikacjami internetowymi. Zabezpieczenie usług tego środowiska można zintegrować niezależnie od platform i języków programowania.

    Diagram mechanizmów wykorzystywanych przy zabezpieczeniach środowiska grid poprzez Web Service
    Rys. 6.3. Diagram mechanizmów wykorzystywanych przy zabezpieczeniach środowiska grid poprzez Web Service [27,51,61]

    Standardy bezpieczeństwa wciąż się rozwijają, tworzone są nowe specyfikacje, modyfikowane lub rozszerzane stare. Wybór odpowiedniego standardu zabezpieczeń w strukturze grid musi być uzależniony od specyfiki, charakteru i przeznaczenia systemu.

    6.10. Wykaz literatury

    1. http://www.ibm.com/developerworks/webservices/library/ws-add/
    2. ftp://www.software.ibm.com/software/developer/library/ws-notification/WSBaseN.pdf
    3. ftp://www.software.ibm.com/software/developer/library/ws-notification/WSBrokeredN.pdf
    4. http://www.106.ibm.com/developerworks/library/ws-pubsub/WS-PubSub.pdf
    5. http://www.106.ibm.com/developerworks/library/ws-resource/ws-modelingresources.pdf
    6. http://www.106.ibm.com/developerworks/library/ws-resource/ws-resourceproperties.pdf
    7. http://www.106.ibm.com/developerworks/library/wsresource/ws-resourcelifetime.pdf
    8. ftp://www.software.ibm.com/software/developer/library/ws-notification/WSTopics.pdf
    9. RFC 2617
    10. RFC 2246
    11. Nadalin A., Kaler C., Hallam-Baker P., Monzillo R. (eds), OASIS Web Services Security: SOAP Message Security 1.0, OASIS Standard Specification, http://docs.oasis-open.org/wss/2004/01/oasis-200401-wsssoap-message-security-1.0.pdf, 2004.
    12. Public Key Infrastructure, Wikipedia, http://en.wikipedia.org/wiki/Public_key_infrastructure
    13. Public Key Certificate, Wikipedia, http://en.wikipedia.org/wiki/Public_key_certificate
    14. Certificate Authority, Wikipedia, http://en.wikipedia.org/wiki/Certificate_authority
    15. Franks J., Hallam-Baker P., Hostetler J., Lawrence S. et al.: RFC 2617: HTTP Authentication: Basic and Digest Access Authentication, http://www.ietf.org/rfc/rfc2617.txt, 1999.
    16. Anderson A.: An Introduction to the Web Services Policy Language (WSPL), w materiałach konferencyjnych 5th IEEE International Workshop on Policies for Distributed Systems and Networks, Yorktown Heights, New York, http://research.sun.com/projects/xacml/Policy2004.pdf, 2004
    17. Larmouth J., ed.: OASIS XML Common Biometric Format, OASIS Standard Specification, http://www.oasis-open.org/committees/download.php/3353/oasis-200305-xcbf-specification-1.1.doc, 2003
    18. Bialkowski J., Heineman K.: OASIS Application Vulnerability Description Language v1.0, Oasis Standard, http://www.oasis-open.org/committees/download.php/7145/AVDL%20Specification%20V1.pdf, 2004
    19. Gralla P.: THE WEB SERVICES ADVISOR: XML Firewalls, http://searchwebservices.techtarget.com/tip/1,289483,sid26_gci855052,00.htm,2002
    20. Koch C., The Battle for Web Services, CIO Magazine, http://www.cio.com/archive/100103/standards.html, 2003
    21. Siddiqui B.: Web Services Security, Part 3, http://webservices.xml.com/pub/a/ws/2003/05/13/security.html, 2003
    22. Siddiqui B., Web Services Security, Part 4, http://webservices.xml.com/pub/a/ws/2003/07/22/security.html, 2003
    23. Nadalin A., Kaler C., Monzillo R., Hallam-Baker P. (eds.): OASIS Web Services Security: SOAP Message Security 1.1, OASIS Standard Specification, http://www.oasisopen.org/committees/download.php/16790/wss-v1.1-spec-os-SOAPMessageSecurity.pdf, 2006
    24. Hallam B., Maler E. (eds.): Assertions and Protocol for the OASIS Security Assertion Markup Language (SAML), OASIS Standard Specification, http://www.oasisopen.org/committees/download.php/2290/oasis-sstc-saml-1.0.zip, 2002
    25. Maler E., Mishra P., Philpot R. (eds.): Assertions and Protocol for the OASIS Security Assertion Markup Language (SAML) V1.1, OASIS Standard Specification, http://www.oasisopen.org/committees/download.php/3406/oasis-sstc-saml-core-1.1.pdf, 2003
    26. Cantor S., Kemp J., Philpot R., Maler E. (eds.): Assertions and Protocol for the OASIS Security Assertion Markup Language (SAML) V2.0, OASIS Standard Specification, http://docs.oasisopen.org/security/saml/v2.0/saml-core-2.0-os.pdf, 2005
    27. Lockhart H.: Demystifying Security Standards, http://dev2dev.bea.com/pub/a/2005/10/security_standards.html, 2005
    28. Godik S., Moses T., (eds.): OASIS eXtensible Access Control Markup Language (XACML) Version 1.0, OASIS Standard Specification, http://www.oasis-open.org/committees/download.php/2406/oasis-xacml-1.0.pdf, 2003
    29. Godik S., Moses T., (eds.): OASIS eXtensible Access Control Markup Language (XACML) Version 1.1, OASIS Committee Specification, http://www.oasis-open.org/committees/xacml/repository/cs-xacmlspecification-1.1.pdf, 2003.
    30. Moses T., (ed.): OASIS eXtensible Access Control Markup Language (XACML) Version 1.1, OASIS Standard Specification, http://docs.oasis-open.org/xacml/2.0/access_control-xacml-2.0-core-spec-os.pdf, 2005
    31. XrML 2.0 Technical Overview, http://www.xrml.org/reference/XrMLTechnicalOverviewV1.pdf, 2002
    32. Eastlake D., Reagle J., Solo D. (eds.): XML Signature Syntax and Processing, W3C Recommendation, http://www.w3.org/TR/xmldsig-core/, 2002
    33. Eastlake D., Reagle J. (eds.): XML Encryption Syntax and Processing. W3C Recommendation, http://www.w3.org/TR/xmlenc-core/, 2002.
    34. Rosenberg R.: Trust, Access Control, and Rights for Web Services Part 2, http://www.devshed.com/c/a/Security/Trust-Access-Control-and-Rights-for-Web-Services-Part-2/, 2004.
    35. Anderson S., Bohren J. et al.: Web Services Trust Language (WS-Trust), ftp://www6.software.ibm.com/software/developer/library/ws-trust.pdf, 2005
    36. Rosenberg R.: Trust, Access Control, and Rights for Web Services Part 1, http://www.devshed.com/c/a/Security/Trust-Access-Control-and-Rights-for-Web-Services-Part-1/, 2004
    37. Security in a Web Services World: A Proposed Architecture and Roadmap, ftp://www6.software.ibm.com/software/developer/library/ws-secmap.pdf, 2002
    38. Anderson S., Bohren J. et al.: Web Services Secure Conversation Language (WSSecureConversation), ftp://www6.software.ibm.com/software/developer/library/ws-secureconversation.pdf, 2005.
    39. OASIS Web Services Secure Exchange (WS-SX) Technical Committee, http://www.oasisopen.org/committees/tc_home.php?wg_abbrev=ws-sx
    40. Siddiqui B.: Web Services Security, Part 1, http://webservices.xml.com/pub/a/ws/2003/03/04/security.html, 2003
    41. Foster, C. Kesselman, (ed.): The Grid 2: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers, 2004
    42. Siddiqui B., Web Services Security, Part 2, http://webservices.xml.com/%20pub/a/ws/2003/04/01/security.html, 2003
    43. Bajaj S., Della-Libera G. (et al.): Web Services Federation Language (WS-Federation), ftp://www6.software.ibm.com/software/developer/library/ws-fed.pdf, 2003
    44. Liberty Alliance ID-WSF 2.0 Specifications Overview, http://xml.coverpages.org/ni2005-02-11-%20b.html#LA20-Specs
    45. Angal R., Narayaan S., Patterson P., Simhachalam M.: Building Identity-Enables Web Services, http://developers.sun.com/prodtech/identserver/reference/techart/id-enabled-ws.html, 2005
    46. Liberty Alliance & WS-Federation: A Comparative Overview, Liberty Alliance Project Wite Paper, https://www.projectliberty.org/resources/whitepapers/wsfed-liberty-overview-10-13-03.pdf, 2003
    47. Drees S.: OASIS Digital Signature Service Core Protocols, Elements, and Bindings, 3rd OASIS Committee Draft, http://docs.oasis-open.org/dss/v1.0/dss-v1.0-spec-cd-Core-r03.pdf, 2005
    48. Ford W. (et al.): XML Key Management Specification (XKMS), W3C Note, http://www.w3.org/TR/xkms/, 2001
    49. Bajaj S. (et al.): Web Services Policy Framework (WS-Policy), http://download.boulder.ibm.com/ibmdl/pub/software/dw/specs/ws-polfram/ws-policy-2006-03-01.pdf, 2006
    50. Box D. (et al.): Web Services Policy Assertions Language (WS-PolicyAssertions), ftp://www6.software.ibm.com/software/%20developer/library/ws-polas.pdf, 2002
    51. Della-Libera G. (et al.): Web Services Security Policy Language (WS-SecurityPolicy), ftp://www6.software.ibm.com/software/developer/library/ws-secpol.pdf, 2005.
    52. Bajaj S. (et al.): Web Services Policy Attachment (WS-PolicyAttachment), http://download.boulder.ibm.com/ibmdl/pub/software/dw/specs/ws-polatt/ws-polat-2006-03-01.pdf, 2006
    53. Moses T. (ed.): OASIS XACML profile for Web-Services, OASIS Working draft, http://www.oasisopen.org/committees/download.php/3661/draft-xacml-wspl-04.pdf, 2003
    54. Halfhill T.: Parallel Processing With CUDA, Microprocessor Report, 2008
    55. Challengers Consortium: Impact of Grids, Draft Research Agenda and Roadmap, Sixth Framework Program, IST 2005 2.5.4, 2008
    56. Technology firms in the recession, Here we go again, The Economist, 2009
    57. TOP500 Supercomputing Sites, http://www.top500.org/
    58. Baker M.: Cluster Computing White Paper, University of Portsmouth, 2000
    59. Snir M., Gropp W.: MPI: The Complete Reference, The MIT Press, 1998
    60. Kesselman C., Foster I. (ed.), The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers, 1998
    61. Foster I.: What is the Grid? A Three Point Checklist, GRID today, 2002
    62. Sotomayor B., Childers L.: Globus Toolkit 4: Programming Java Services, Morgan Kaufmann, 2005
    63. Barrett B.P.: Introduction to WS Authorization

  • Analiza istniejących obliczeń uruchamianych w ramach systemów rozproszonych

    W rozdziale zaprezentowano analizę algorytmów równoległych tradycyjnie uruchamianych w systemach klastrowych wysokiej wydajności, a następnie pokazano charakterystykę algorytmów ze względu na parametry istotne przy implementacji ich rozwiązań w rozproszonym środowisku Comcute. Następnie przedstawiono ocenę możliwości ich przeniesienia do tego środowiska.

    4.1. Tradycyjne paradygmaty przetwarzania równoległego – sposób rozpraszania zadań, obliczeń i danych

    Tradycyjne algorytmy [12-15] uruchamiane w systemach równoległych można podzielić ze względu na paradygmaty przetwarzania, podziału danych i synchronizacji. Wyróżnić można przetwarzanie typu:

    • embarrassingly parallel – obliczenia lub dane mogą zostać podzielone na niezależne fragmenty i rozproszone przed wykonaniem obliczeń równoległych (rys. 4.1). Wysoka skalowalność.
    Przetwarzanie typu embarrassingly parallel
    Rys. 4.1. Przetwarzanie typu embarrassingly parallel
    • master-slave/task farming – proces-master dzieli dane wejściowe i/lub obliczenia na fragmenty, których przetworzenie zleca procesom typu slave (rys. 4.2). Podział i dystrybucja mogą być wykonane statycznie bądź dynamicznie.
    Przetwarzanie typu master-slave
    Rys. 4.2. Przetwarzanie typu master-slave
    • single program multiple data (SPMD)/geometric parallelism – wiele procesów lub wątków aplikacji wykonuje te same obliczenia (stąd określenie Single Program) na różnych danych (stąd Multiple Data) – rys. 4.3 Zwykle obliczenia tego typu polegają na podziale dużej przestrzeni danych wejściowych na procesy/wątki i rozwiązywanie fragmentów równolegle z następującą zaraz później synchronizacją danych. Przykładem może być wiele problemów fizycznych, takich jak aplikacje symulujące zmiany pogodowe w danym fragmencie przestrzeni, zjawiska zachodzące np. w organizmie ludzkim, rozchodzenie się fal w przestrzeni, rozprzestrzenianie się skażeń promieniotwórczych lub biologicznych, czy inne aplikacje, w których przestrzeń modelowana jest przez podział na wiele komórek zależnych od komórek sąsiednich. Wydajne zrównoleglanie wymaga tutaj w szczególności krótkich opóźnień komunikacyjnych, w szczególności dla uzyskania wysokiej skalowalności dla dużej liczby procesorów. W paradygmacie tym następuje podział przestrzeni na fragmenty przydzielone różnym procesom. Procesy komunikują się ze sobą. Symulacja często polega na pętli zawierającej przeplatające się obliczenia i komunikację
    Przetwarzanie typu SPMD
    Rys. 4.3. Przetwarzanie typu SPMD
    • przetwarzanie potokowe – wyróżnia się niezależne fragmenty przetwarzania (polegające zwykle na uruchomieniu innego kodu), które wykonywane są po kolei na danych wejściowych. Dane wejściowe to zwykle wiele paczek danych, które są kolejno podawane do kolejnych punktów przetwarzania w potoku (rys. 4.4).
    Przetwarzanie potokowe
    Rys. 4.4. Przetwarzanie potokowe
    • dziel-i-rządź – początkowy problem dzielony jest na podproblemy (często dzielone są przy tym dane wejściowe). Dalej następuje rekurencyjny podział danych/problemu na fragmenty/podproblemy (rys. 4.5).
    Przetwarzanie typu dziel i rządź
    Rys. 4.5. Przetwarzanie typu dziel i rządź

    4.2. Cele równoległego uruchomienia w kontekście środowiska Comcute

    Systemy równoległe takie jak superkomputery, wysokowydajne klastry czy lokalne sieci komputerowe wykorzystywane są do uruchamiania aplikacji równoległych lub sekwencyjnych operujących na niezależnych fragmentach danych w celu:

    • Zmniejszenia czasu rozwiązania problemu. Prawo Amdahla określa przyspieszenie obliczeń możliwe do uzyskania w takim systemie rozpatrując fragment rozwiązania, który można zrównoleglić oraz fragment sekwencyjny. Przyspieszeniem obliczeń określa się stosunek czasu wykonania w systemie z jednym procesorem i czasu wykonania w systemie równoległym. Podział danych na fragmenty, które mogą być przetworzone równolegle przez różne jednostki systemu równoległego pozwala na skrócenie czasu wykonania obliczeń.

    • Zwiększenia niezawodności przetwarzania poprzez uruchomienie wielu instancji rozwiązania dla tych samych danych. W przypadku awarii, czy też zwrócenia różnych wyników przez różne instancje, mechanizm głosowania może zadecydować o wyniku bądź konieczności powtórzenia obliczeń.

    • Weryfikacji wyników poprzez równoległe uruchomienie różnych algorytmów rozwiązujących danych problem dla tych samych danych wejściowych. Porównanie wyników pozwala ocenić ich wiarygodność.

    • Możliwości rozwiązania problemu wymagającego przetworzenia danych dużych rozmiarów. W wielu przypadkach problem dla danych dużych rozmiarów nie może zostać rozwiązany na pojedynczym komputerze, gdyż system nie jest w stanie wydajnie przetworzyć danych dużych rozmiarów. Oczywiście, wydajność zależy również od sposobu zarządzania danymi w samym algorytmie.

    Wszystkie powyższe cele mogą być również pożądane w kontekście uruchomienia danego problemu w rozproszonym środowisku Comcute pod warunkiem, że system będzie w stanie wydajnie dany algorytm uruchomić (patrz punkt 4.3 poniżej).

    4.3. Istotne parametry przy migracji tradycyjnych obliczeń na środowisko Comcute

    Bazując na ww. prawie Amdahla, z punktu widzenia wydajności równoległego czy rozproszonego wykonania algorytmu istotne są wartości związane z:

    • czasem przetwarzania,
    • czasem komunikacji,
    • kosztem i częstotliwością synchronizacji.

    Parametry te będą determinowały skalowalność algorytmów w środowiskach rozproszonych, w których czas komunikacji w stosunku do czasu obliczeń będzie znacznie większy niż dla tego samego rozwiązania uruchomionego w systemach klastrowych.

    Z tego punktu widzenia, istotne parametry sieci komunikacyjnej to:

    • przepustowość (ang. bandwidth) – zdolność łącza komunikacyjnego do przesłania określonej ilości danych w jednostce czasu,
    • startup time – czas niezbędny na zainicjowanie połączenia.

    Typowe wartości uzyskiwane dla klastrów bazujących na sieci Gigabit Ethernet to 100 MB/s oraz opóźnienia rzędu 50-80μs, zaś dla wydajnych klastrów z siecią Infiniband 1000 MB/s oraz 1-5 μs.

    Z kolei, przepustowości dla komunikacji klient-serwer w Internecie mają zwykle wartości od kilku KB/s do około 10-20 Mbit/s dla szerokopasmowych łącz i na wybranych fragmentach sieci.

    Stąd też, analiza możliwości przeniesienia tradycyjnych algorytmów z systemów klastrowych do systemu Comcute powinna uwzględniać:

    1. paradygmaty przetwarzania:
      • embarrassingly parallel [11],
      • master-slave [11],
      • single program multiple data [5],
      • pipeline [11],
      • divide-and-conquer [3-4,6].

      Ze względu na proponowaną architekturę systemu algorytmy, które będą wstępnie predysponowane do zrównoleglenia powinny działać w jednym w paradygmatów: embarrassingly parallel, master-slave lub divide-and-conquer.

    2. typowe rozmiary danych wejściowych,

    3. typowe rozmiary danych wyjściowych,

    4. typowa liczba procesorów/rdzeni, na których uruchamia się algorytm

    5. stosunek czasu obliczeń do czasu komunikacji w algorytmie – przy danym rozmiarze danych wejściowych jest to zwykle zależne od liczby procesorów, na których się uruchamia daną aplikację przy zadanym rozmiarze danych wejściowych. Dla dużej liczby procesorów coraz większe znaczenie odgrywa opóźnienie komunikacyjne, w szczególności dla paradygmatów takich jak SPMD. Tradycyjnie, zrównoleglając zadania, stosunek ten powinien być możliwie duży. W innym przypadku, zrównoleglanie może być nieopłacalne w porównaniu do uruchomienia na pojedynczej maszynie. W tym przypadku, rozpatrzmy możliwość zrównoleglania krótkotrwałych zadań pomiędzy użytkowników – zadań, dla których czas komunikacji będzie znaczący. Z jednej strony, przy bardzo dużej liczbie klientów daje to możliwość rozproszenia obliczeń i nawet długi czas komunikacji może być akceptowalny przy bardzo dużym rozmiarze danych oraz bardzo dużej liczbie klientów. Z drugiej, powodować może nadmierne obciążenie serwera/serwerów rozpraszających, które będą musiały obsługiwać bardzo dużą liczbę zgłoszeń po zadania oraz z wynikami od bardzo dużej liczby klientów w zadanym przedziale czasowym.

    6. synchronizacja w algorytmie:
      • globalna,
      • lokalna (partycje synchronizujące się lokalnie),
      • brak (podział danych wejściowych i zebranie wyników),

      Najprawdopodobniej ze względu na ograniczenia technologiczne (domyślne ograniczenia do komunikacji klienta z serwerem, z którego pobrany został kod klienta) synchronizacja musiałaby odbywać się poprzez scentralizowaną bądź hierarchicznie skonfigurowaną część serwerową systemu Comcute. W zależności od liczby klientów, liczby uruchomionych aplikacji mogłaby powodować zbyt duże obciążenie systemu i uniemożliwiać wykonanie.

    7. złożoność algorytmu (ew. NP-zupełny) algorytm:
      • optymalny – w dużym systemie takim jak Comcute z tysiącem, dziesiątkami lub setkami tysięcy klientów rozwiązanie problemu nawet NP-zupełnego dla dużych zbiorów danych może być realne. Co więcej, dla paradygmatów przetwarzania embarrassingly parallel, master-slave lub divide-and-conquerbez interakcji pomiędzy problemami, może się dobrze skalować.
      • heurystyczny – rozwiązanie przybliżone stosowane jest zwykle ze względu na to, żeby skrócić czas wykonania algorytmu. Ze względu na potencjalnie dużą liczbę klientów, można rozważyć zastosowanie prostego, dobrze skalującego się rozwiązania optymalnego. Zależne od algorytmu.
      • losowe rozwiązania – w tak dużym systemie możliwe jest szukanie rozwiązań np. problemów kombinatorycznych poprzez losowe generowanie rozwiązań przez potencjalnie bardzo dużą liczbę klientów i porównywanie wyników. Bardziej dokładną alternatywą może być podział przestrzeni danych wejściowych na fragmenty i przydzielenie do poszczególnych klientów.
    8. typowe rozmiary danych przesyłanych pomiędzy węzłami (klastra) i częstotliwość synchronizacji – istotne w kontekście pytania ilu klientów może się synchronizować w tym momencie przez system Comcute i czy z powodu rozmiaru danych i ew. dużej częstotliwości nie stanie się to wąskim gardłem systemu.

    9. typowy czas działania algorytmu – zwykle algorytmy działające dłużej (ze względu na swoją złożoność bądź zwykle stosowane rozmiary danych wejściowych) będą prezentowały większy potencjał zrównoleglania w środowisku Comcute niż algorytmy działające krócej. Wynika to z potencjalnie dużych czasów komunikacji w rozproszonym środowisku Comcute.

    4.4. Charakterystyki istniejących systemów i standardów obliczeniowych – w kontekście migracji algorytmów do systemu Comcute

    Potencjalne przeniesienie algorytmów z tradycyjnych systemów klastrowych na rozproszony system Comcute wiąże się bezpośrednio z technologią kodowania, kompilacji i uruchomienia tego typu aplikacji. Tradycyjnie wykorzystuje się niskopoziomowe programowanie równoległe na klastrach – m.in. następujące modele i interfejsy programistyczne oraz środowiska:

    1. programowanie w modelu z pamięcią współdzieloną – poszczególne procesy aplikacji bądź wątki działające w obrębie procesu mają dostęp do wspólnej przestrzeni w pamięci. Synchronizacja może następować przez zapis i odczyt w komórkach pamięci współdzielonej z dodatkowymi mechanizmami synchronizacji takimi jak monitory, blokady, zmienne warunkowe, zasypianie i budzenie wątków etc. Przykładami technologii implementującymi ten model są np.:
      • Pthreads – API wspierające wielowątkowość w języku C.
      • Java Threads – API wspierające wielowątkowość w języku Java.
      • OpenMP – możliwość rozszerzania programów o sekcje wykonywane równolegle poprzez ich specyfikację za pomocą specjalnych dyrektyw i deklaracji.
    2. programowanie w modelu z pamięcią rozproszoną. Najczęściej stosowany jest model z przekazywaniem wiadomości (message passing).
      • MPI [2] – popularna specyfikacja z przekazywaniem wiadomości, również wsparciem dla wielowątkowości, API dla języków C/C++ i Fortran.
      • PVM [1] – środowisko przetwarzania równoległego i rozproszonego dla języka C/C++ i Fortran.

    Zwykle kompilacja tego typu zadań wykonywana jest przez programistę-użytkownika, który następnie uruchamia aplikację równoległą na dedykowanej maszynie wirtualnej lub wykorzystuje do uruchomienia systemy kolejkowe takie jak PBS, LSF itp.

    W literaturze wymienia się wysokopoziomowe oprogramowanie i wzorce do automatycznego zrównoleglania pewnych klas algorytmów takich jak:

    1. divide-and-conquer – np. Cilk dla języka C, Satin [9] dla języka Java, DAMPVM/DAC [4] dla języka C++.
    2. single program multiple data (SPMD) – ParMETIS, Zoltan.

    Aplikacje równoległe mogą być także uruchamiane na wielu klastrach za pomocą narzędzi takich jak MPICH-G2, PACX-MPI lub BC-MPI.

    Z racji tego, że wyżej wymienione narzędzia wymagają specjalistycznej wiedzy, powstało wiele systemów pozwalających na uruchamianie aplikacji równoległych (przygotowanych często dla użytkownika) dla zadanych danych z wykorzystaniem łatwego w użyciu interfejsu. Zasoby wykorzystywane przez tego typu systemy gridowe są ukryte przed użytkownikiem, który jedynie zleca zadania do wykonania i oczekuje na wyniki. System dokonuje wyboru zasobów spełniających wymagania tj. np. architektura procesora, na której może być uruchamiany plik wykonywalny, rozmiar dostępnej pamięci RAM oraz przestrzeni dyskowej, po czym dokonuje rezerwacji zasobów, kopiuje podane przez użytkownika dane wejściowe, uruchamia aplikację (sekwencyjnie bądź równolegle), z powrotem przesyła dane wyjściowe do użytkownika. Tego typu systemy wykorzystują często tzw. warstwę pośrednią grid jak np. Globus Toolkit, Unicore etc.

    Pewnym rozwinięciem tego typu przetwarzania jest cloud computing gdzie dostawca oferuje użytkownikowi całą platformę, infrastrukturę bądź oprogramowanie w zadanej konfiguracji, na określony czas, za określoną kwotę. Użytkownik może dostosowywać system do swoich potrzeb kontrolując jednocześnie koszt zasobów i oprogramowania. Nie musi wówczas utrzymywać całego środowiska samodzielnie.

    Z kolei przetwarzanie typu volunteer computing wykorzystuje komputery internautów do podzielenia danych wejściowych dużego problemu (master-slave) na fragmenty i zlecenia ich przetwarzania użytkownikom. Kwestie z tym związane dotyczą:

    1. wiarygodności przetwarzania – obliczenia muszą być zlecane niezależnym klientom i wyniki porównywane,

    2. tylko pewna klasa algorytmów (możliwa do uruchomienia w paradygmacie master-slave) może być efektywnie zrównoleglona,

    3. ograniczeń po stronie klienta – użytkownik musi jawnie zainstalować kod zarządzający i aplikacji na swoim komputerze, wyrazić zgodę na uruchomienie i określić warunki wykorzystania,

    4. użytkownicy zwykle nie są wynagradzani finansowo za uczestnictwo w projekcie, mają natomiast świadomość współuczestnictwa w ważnych projektach.

    Bardzo często implementacje algorytmów wykorzystują zewnętrzne biblioteki do wykonania pewnych operacji lub części algorytmów – np. sortowanie, operacje na macierzach, przetwarzanie obrazów etc. Powstaje kwestia możliwości wykorzystania tego typu bibliotek po stronie klienta w aplikacji systemu Comcute. Konkretna technologia może ograniczyć możliwość wykorzystania danej biblioteki bądź wymusić implementację w innym języku (np. migrację do języka Java jeśli strona klienta systemu Comcute wykorzysta technologię apletów Javy itp.). Bardzo wiele programów równoległych implementowanych jest w językach C/C++ lub Fortranie. Istnieje wiele często wykorzystywanych bibliotek zaimplementowanych w tych językach.

    W kontekście systemu Comcute, wymaga to albo nowego sposobu kodowania algorytmów z uwzględnieniem języka wykorzystywanego przez daną technologię bądź możliwości uruchomienia kodu po stronie klienta, albo specjalnych nakładek na istniejące API, co wydaje się kłopotliwe.

    Problemy w Comcute:

    1. podział danych – jaki – statyczny/dynamiczny,
    2. język kodowania algorytmów,
    3. repozytorium algorytmów,
    4. technologia uruchamiania.

    Na ile łatwo zmigrować już istniejący kod do tego typu środowiska? Implementacje aplikacji z systemów typu BOINC [16] do konkretnej technologii przez przeglądarkę będą możliwe do przeniesienia z uzyskaniem istotnego przyspieszenia obliczeń. Będzie to możliwe dla aplikacji w paradygmatach embarrassingly parallel oraz master-slave z dużym stosunkiem czasu obliczeń do komunikacji i synchronizacji, w mniejszym stopniu dla aplikacji dziel-i-rządź. Aplikacje SPMD oraz potokowe nie będą pracowały wydajnie w środowisku Comcute chyba, że system zostanie wykorzystany do uruchamiania całych instancji z różnymi danymi wejściowymi u różnych internautów. W takim przypadku Comcute pozwoli na równoległe obliczenie wielu scenariuszy z różnymi danymi wejściowymi.

    4.5. Charakterystyka wybranych algorytmów

    W rozdziale przedstawiono charakterystykę wybranych i często używanych algorytmów równoległych (uruchamianych do tej pory na klastrach, sieciach LAN), pod kątem możliwości uruchomienia w środowisku rozproszonym (tj. takim gdzie koszty komunikacji są relatywnie większe niż na klastrach), a więc możliwości uruchomienia w środowisku Comcute.

    4.5.1. Równoległe symulacje SPMD

    Zwykle równoległe aplikacje rozwiązujące układ równań różniczkowych – sprowadzone do liniowych równań rozwiązywanych w czasie równolegle.

    Paradygmat przetwarzania
    single program multiple data
    Dane wejściowe
    zwykle przestrzeń 2D lub 3D podzielona na fragmenty – możliwy podział statyczny lub dynamiczny
    Wynik
    wartości danych w przestrzeni o rozmiarze takim jak dane wejściowe
    Typowe rozmiary danych wejściowych
    np. 1000x1000x1000x kilka zmiennych
    Typowe rozmiary danych wyjściowych
    jak dane wejściowe
    Typowa liczba procesorów/ rdzeni, na których uruchamia się algorytm
    1-256
    Stosunek czasu obliczeń do czasu komunikacji w algorytmie
    taki, który pozwala na wydajność rzędu 0,5-0,8 na 32-64 procesorach (przetwarzanie z pamięcią rozproszoną)
    Synchronizacja w algorytmie
    Zwykle lokalna, może być globalna np. co pewną liczbę iteracji
    Liczba synchronizacji
    synchronizacja co 1 iterację algorytmu
    Złożoność algorytmu
    przybliżone rozwiązanie
    Algorytm
    heurystyczny
    Typowe rozmiary danych przesyłanych pomiędzy węzłami
    zależy od liczby procesorów, ale rzędu rozmiaru wymiaru przestrzeni bazowej
    Typowy czas działania algorytmu
    zależy od dokładności, może być od kilku godzin do wielu dni
    Znane implementacje algorytmu
    publikacje w literaturze raportu
    Istniejące implementacje – licencja + język programowania
    oprogramowanie ułatwiające implementację + algorytmy zrównoleglania np. Zoltan, ParMETIS

    4.5.2. Dziel-i-rządź

    Schemat pozwalający na złożone i często nieregularne obliczenia np. przeszukiwanie drzew w grach etc.

    Paradygmat przetwarzania
    divide-and-conquer
    Dane wejściowe
    może to być pojedynczy wektor rozmiaru n (np. sortowanie) i/lub pewne globalne dane – np. szachownica do przeszukiwania ruchów
    Wynik
    zwykle wartości danych w przestrzeni o rozmiarze takim jak dane wejściowe
    Typowe rozmiary danych wejściowych
    od kilkunastu-kilkuset zmiennych do dziesiątek setek tysięcy
    Typowe rozmiary danych wyjściowych
    jak dane wejściowe
    Typowa liczba procesorów/ rdzeni, na których uruchamia się algorytm
    1-256
    Stosunek czasu obliczeń do czasu komunikacji w algorytmie
    zależy od algorytmu – głównie zależy od czasu podziału/ scalania danych oraz obliczeń wykonywanych w węzłach, duży dla np. rozwiązywania gier typu szachy/ warcaby
    Synchronizacja w algorytmie
    Zwykle brak, ale może też być okazjonalna synchronizacja lokalna i globalna
    Liczba synchronizacji
    zwykle podział na podproblemy i zebranie wyników, może być okazjonalna synchronizacja globalna (np. równoległy algorytm alfa-beta)
    Złożoność algorytmu
    zwykle pełne przeszukiwanie przestrzeni rozwiązań, mogą być odcięcia jak w algorytmach alfa-beta
    Algorytm
    optymalny
    Typowe rozmiary danych przesyłanych pomiędzy węzłami
    od kilkunastu / kilkuset zmiennych do dziesiątek setek tysięcy, ale stosunkowo rzadka komunikacja o ile czas obliczeń w węzłach wystarczająco długi, problem przy skalowaniu gdy czasy te są krótkie i jeszcze dodatkowo nieznane z góry
    Typowy czas działania algorytmu
    zależy od problemu, może być od kilku godzin do wielu dni
    Znane implementacje algorytmu
    publikacje w literaturze raportu
    Istniejące implementacje – licencja + język programowania
    różne frameworki dla różnych języków programowania – do automatycznego zrównoleglania również np. Satin, Cilk, DAMPVM/DAC

    4.5.3. Sortowanie quick-sort

    Często wykorzystywany algorytm sortowania oparty na porównywaniu.

    Paradygmat przetwarzania
    divide-and-conquer
    Dane wejściowe
    wektor rozmiaru n
    Wynik
    wektor rozmiaru n
    Typowe rozmiary danych wejściowych
    od kilkunastu do wielu tysięcy lub więcej zmiennych
    Typowe rozmiary danych wyjściowych
    od kilkunastu do wielu tysięcy lub więcej zmiennych
    Typowa liczba procesorów/ rdzeni, na których uruchamia się algorytm
    Kilka-kilkadziesiąt
    Stosunek czasu obliczeń do czasu komunikacji w algorytmie
    duży przy dużym wektorze wejściowym, algorytm naturalnie dzieli problem wejściowy na podproblemy (dziel i rządź)
    Synchronizacja w algorytmie
    brak w dziel i rządź
    Liczba synchronizacji
    brak pośrednich, podział danych i zebranie wyników
    Złożoność algorytmu
    O(nlogn)
    Algorytm
    optymalny
    Typowe rozmiary danych przesyłanych pomiędzy węzłami
    O(n)
    Typowy czas działania algorytmu
    bardzo szybki algorytm, sekundy, minuty
    Znane implementacje algorytmu
    książki o tematyce HPC
    Istniejące implementacje – licencja + język programowania
    wiele implementacji dostępnych, np. w bibliotekach do C, wiele implementacji dla różnych języków

    4.5.4. Wyszukiwanie wzorca tekstowego w pliku/plikach

    Wyszukiwanie wzorca w jednym lub wielu danych plikach.

    Paradygmat przetwarzania
    single program multiple data, pipeline Dane wejściowe
    pliki do przeszukania i wzorzec (zwykle znacznie mniejszy)
    Wynik
    fragmenty plików bądź też indeksy
    Typowe rozmiary danych wejściowych
    wzorce rzędu kilku, kilkuset, kilku tysięcy bajtów, pliki o rozmiarach megabajtów
    Typowe rozmiary danych wyjściowych
    indeksy znalezionych fragmentów bądź fragmenty plików
    Typowa liczba procesorów/ rdzeni, na których uruchamia się algorytm
    1-256
    Stosunek czasu obliczeń do czasu komunikacji w algorytmie
    zwykle duży – dobrze się zrównolegla
    Synchronizacja w algorytmie
    brak
    Liczba synchronizacji
    niewiele, podział danych i zebranie wyników, może być dynamiczny master-slave
    Złożoność algorytmu
    pełne przeszukiwanie
    Algorytm
    optymalny
    Typowe rozmiary danych przesyłanych pomiędzy węzłami
    rzędu rozmiarów plików wejściowych, ale dane mogą być przesyłane bądź na początku i na końcu działania aplikacji bądź też dosyłane fragmentami – dynamiczny master-slave – większa możliwość nakładania obliczeń i komunikacji
    Typowy czas działania algorytmu
    kilka minut – kilka dni
    Znane implementacje algorytmu
    książki o tematyce HPC
    Istniejące implementacje – licencja + język programowania
    programy grep i inne, możliwe wykorzystanie do równoległej implementacji

    4.6. Wykaz literatury

    1. Geist A., Beguelin A., Dongarra J., Jiang W., Mancheck R., Sunderam V.: PVM Parallel Virtual Machine. A Users Guide and Tutorial for Networked Parallel Computing. MIT Press, Cambridge, 1994. http://www.epm.ornl.gov/pvm/
    2. Pacheco P.: Parallel programming with MPI. Morgan Kaufmann. 1996
    3. Czarnul P.: Dynamic Process Partitioning and Migration for Irregular Applications, accepted for International Conference on Parallel Computing in Electrical Engineering PARELEC’2002, Warsaw, Poland, 2002
    4. Czarnul P, Tomko K., Krawczyk H.: Dynamic Partitioning of the Divide-and-Conquer Scheme with Migration in PVM Environment. In Recent Advances in Parallel Virtual Machine and Message Passing Interface, no 2131 in Lecture Notes in Computer Science, pp. 174-182. Springer-Verlag, 8th European PVM/MPI Users’ Group Meeting, Santorini/Thera, Greece, September 23-26, 2001
    5. Sarris C.D., Tomko K., Czarnul P., Shih-HaoHung, Robertson R.L., Donghoon Chun, Davidson E. S., Katehi L.P.B.: Multiresolution Time Domain Modeling for Large Scale Wireless Communication Problems. In Proceedings of the 2001 IEEE AP-S International Symposium on Antennas and Propagation, volume 3, pages 557–560, 2001.
    6. Horowitz E., Zorat A.: Divide-and-conquer for Parallel Processing. IEEE Transactions on Computers, C-32(6):582-585, June 1983.
    7. Schloegel K., Karypis G. Kumar V.: Graph Partitioning for High Performance Scientic Simulations, CRPC Parallel Computing Handbook, Morgan Kaufmann, http://citeseer.nj.nec.com/schloegel00graph.html, 2000
    8. Krawczyk H. Saif J.: Parallel Image Matching on PC Cluster. In Recent Advances in Parallel Virtual Machine and Message Passing Interface, number 2131 in Lecture Notes in Computer Science, pages 312-318. Springer-Verlag, 8th European PVM/MPI Users’ Group Meeting, Santorini/Thera, Greece, September 23-26, 2001
    9. Nieuwpoort R.V. van, Kielmann T., Bal H.E.: Satin: Efficient Parallel Divide-and-Conquer in Java. In Euro-Par 2000 Parallel Processing, Proceedings of the 6th International Euro-Par Conference, no 1900 in LNCS, pp. 690-699, 2000.
    10. Czarnul P.: Programming, Tuning and Automatic Parallelization of Irregular Divide-and-Conquer Applications in DAMPVM/DAC. International Journal of High Performance Computing Applications 17/2003, pp. 77-93, 2003
    11. Wilkinson B., Allen M.: Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice Hall, 1999
    12. Akl S. G.: The design and analysis of parallel algorithms. Prentice Hall, 1989
    13. Foster I.: Designing and Building Parallel Programs. Addison-Wesley, http://www.unix.mcs.anl.gov/dbpp/, 1995
    14. Rajkumar Buyya (ed): High Performance Cluster Computing, Programming and Applications. Prentice Hall, 1999.
    15. Kirk D., Wen-mei Hwu: Programming Massively Parallel Processors. Morgan Kaufmann, 2010
    16. Anderson D. P. BOINC: A system for public-resource computing and storage. 5th IEEE ACM International Workshop on Grid Computing, 2004

  • Berkeley Open Infrastructure for Network Computing

    W rozdziale skoncentrowano się na systemie BOINC (ang. BerkeleyOpen Infrastructure for Network Computing) jako interesującym rozwiązaniu integrującym rozproszone moce obliczeniowe osobistych komputerów typu PC w Internecie. Przedstawiono zasadę działania opisywanej platformy [1]. W dalszej części zaprezentowano kilka wybranych projektów naukowych wykorzystujących BOINC, które są reprezentatywne w zakresie zastosowania systemu w ujęciu założonego paradygmatu przetwarzania. Celem jest wprowadzenie w zagadnienia internetowego przetwarzania rozproszonego ze szczególnym zwróceniem uwagi na aspekty praktyczne. Pokazano szereg realizowanych projektów demonstrujących praktyczne wykorzystanie tego typu rozwiązań w przedsięwzięciach dużej skali [2].

    3.1. Klient w systemie BOINC

    BOINC składa się z programu klienta i serwera danych wykorzystującego bazę danych. BOINC nie jest jednak specjalizowaną aplikacją — to platforma, która może wspierać wiele różnych aplikacji. Dzięki temu można ją wykorzystywać do równoczesnego prowadzenia wielu obliczeń. Klient BOINC (ang. Core Client lub Boinc Daemon) jest programem odpowiedzialnym za komunikację oraz kontrolę nad aplikacjami liczącymi. Klient BOINC jest obecny przez cały czas w pamięci RAM, w przeciwieństwie do Menedżera BOINC, od którego odbiera polecenia, i którym można go konfigurować. To właśnie aplikacja kliencka decyduje jaka próbka i w jakim czasie będzie liczona. Również komunikuje się ona z serwerami projektów naukowych, z których pochodzą próbki.

    3.2. Serwery BOINC

    Oprogramowanie BOINC dzieli się na oprogramowanie pracujące po stronie serwera projektu oraz to uruchamiane na komputerze uczestnika danego projektu naukowego. Do najważniejszych aplikacji serwera należy Scheduler – serwer harmonogramów, który rozdziela fragmenty danych do obliczeń pomiędzy komputery – węzły oraz przyjmuje uzyskane od nich wyniki. Scheduler kontroluje i określa zasoby podczas dystrybucji jednostek. Oznacza to, że serwer nie przydzieli pracy wymagającej większej ilości pamięci RAM, niż komputer użytkownika posiada. Przy podziale pracy uwzględnia się m.in.: ilość pamięci RAM, moc CPU i GPU, średni czas w ciągu doby, jaki komputery liczące przeznaczają na obliczenia, system operacyjny oraz platformę programową (np. MAC, SUN). Dzięki temu słabszy komputer nie zostanie za bardzo obciążony, natomiast mocniejsza maszyna będzie lepiej wykorzystana. W przypadku, kiedy węzeł liczący nie posiada jeszcze zainstalowanej aplikacji przetwarzającej dane, to zostaje ona przesłana do węzła. W obrębie jednego projektu możliwe jest działanie kilku aplikacji, a dane wysyłane przeznaczone są dla jednej z nich. Komputer użytkownika pobiera aplikacje i pliki wejściowe z serwera danych (ang. data serwer) danego projektu. Programy pobierane są od razu po dołączeniu do projektu, przetwarzane są one następnie na komputerach uczestniczących w tym projekcie, pobierają odpowiednie dane i tworzą pliki wyjściowe, które są wysyłane na serwer danych. Komputer użytkownika po zgłoszeniu rezultatów swoich wyników do serwera harmonogramów otrzymuje od niego dalsze instrukcje. Za wykonaną pracę obliczeniową właściciel węzła liczącego otrzymuje punkty.

    3.3. Jednostki obliczeniowe Work Units

    Work Unit (WU) jest angielską nazwą jednostki roboczej lub pakietu, porcją lub próbką danych generowanych przez dany projekt naukowy. Pakiety następnie są „klonowane”, co oznacza, że powstaje kilka identycznych próbek. Wyniki mogą być częścią lub jedną z kopii WU, gdy zastosowana jest redundancja. Próbki rozsyłane są do użytkowników, po czym po wykonaniu przez klienta obliczeń zwraca się je na serwer dedykowany projektu. Odesłane wyniki umożliwiają wybranie wyniku kanonicznego (ang. canonical result), nazywanego również wzorcowym dla danej jednostki roboczej i dodanie go do bazy danych przez aplikację Asymilator (ang. Assimilator). Jest to aplikacja serwera BOINC, która zajmuje się jednostkami roboczymi z zakończonym procesem obliczeń i z wynikiem wzorcowym lub błędnym. Program ten może również prosić o wygenerowanie kolejnej próbki. Istotną funkcją oprogramowaniem BOINC jest „punkt przywracania próbki” – Checkpoint. Polega to zapisaniu dotychczas przetworzonego fragmentu próbki na dysku, dzięki czemu nie będzie liczona od początku po przerwie w obliczeniach.

    Platforma BOINC stosuje redundancję, aby zapobiec powstawaniu potencjalnych błędów w czasie przeliczania próbki na komputerze użytkownika. W celu uzyskania poprawnych wyników rozesłanych próbek, powiela się je, po czym weryfikuje ich zgodność i sprawdza poprawność. Kolejnym komponentem aplikacji BOINC jest tranzycjoner (ang. Transitioner), który zajmuje się przejściami stanów jednostek roboczych oraz próbek. Śledzi on próbki będące w trakcie obliczania, po czym zmienia ich statusy w odpowiednim momencie. Sprawdza czy dana jednostka jest gotowa do wysłania, a także czy dana próbka została rozesłana, czy jest poprawna oraz czy można ją już usunąć. Tranzycjoner ma również możliwość generowania nowych próbek, nadawania statusu jednostki jako nieodwracalnie błędnej, bądź wydawania instrukcji weryfikacji i asymilacji jednostki. BOINC wykorzystuje również redundancję homogeniczną polegającą na tworzeniu klas systemów bądź procesorów, które odsyłają takie same wyniki w ramach danej aplikacji. Uzyskane w ten sposób informacje mają zastosowanie przy wiarygodnym rozsyłaniu próbek.

    3.4. Wybrane projekty

    Z platformy BOINC korzysta wiele projektów z różnych dziedzin nauki [3, 4, 5]. Każdy projekt aplikujący do BOINC jest formalnie i merytorycznie weryfikowany i zatwierdzany. Aplikacja, która uzyska aprobatę Uniwersytetu Kalifornijskiego w Berkeley, otrzymuje unikalny podpis cyfrowy. Od momentu uzyskania podpisu cyfrowego projekt będzie mógł korzystać z zasobów technologii BOINC. Projekty niezweryfikowane mogłyby powodować niestabilną pracę systemu komputera, a ich aplikacje łącząc się z Internetem w celu pobrania danych groziłyby infekcją złośliwego oprogramowania. Projekty działające w sieci muszą być bezpieczne, ponieważ korzystają z udostępnionej im nieodpłatnie wolnej mocy obliczeniowej użytkowników zwykłych komputerów PC [6, 7].

    Pełną aktualną listę projektów można znaleźć na stronie Uniwersytetu w Berkeley. Jak do tej pory platforma BOINC nie została jeszcze użyta w celu rozpowszechnienia złośliwego oprogramowania.

    3.4.1. SETI@home Classic

    Program SETI został zapoczątkowany 19 września 1959 roku. W artykule zatytułowanym „Searching for Interstellar Communications” opublikowanym w Nature przez dwóch młodych fizyków Philipa Morrisona i Giuseppe Cocconi’ego została opisana możliwość komunikowania się w przestrzeni kosmicznej za pomocą fal radiowych o długości 21 cm (1420MHz).

    W SETI@home występuje redundancja obliczeń, każdy pakiet danych jest przetwarzany wielokrotnie, co pozwala wykryć i odrzucić wyniki generowane przez uszkodzone lub fałszywe programy klienckie. Poziom nadmiarowości obliczeń wzrasta wraz z liczbą klientów i ich średnią prędkością, ponieważ pakiety wytwarzane są w ograniczonym tempie. Ilości danych nadmiarowych wzrastają w ciągu życia projektu. Poprzez zwiększanie liczby obliczeń wykonywanych przez klienta dla pojedynczej próbki utrzymywany jest poziom nadmiarowości mieszczący się w środku skali zapotrzebowania. Pakiety tworzy i dystrybuuje kompleksowy serwer w laboratorium. Jednostki robocze powstają poprzez podzielenie 2,5MHz sygnału na 256 przedziałów, każdy szerokości około 10kHz. Następnie każdy taki przedział jest dzielony na 100 sekundowe segmenty, zachodzące na siebie na 20 sekund, czyli szukany sygnał będzie się zawierał przynajmniej w jednej próbce. Próbki mają po 350KB. Do przechowywania informacji o próbkach, wynikach, użytkownikach, etc. dotyczących projektu stosowana jest relacyjna baza danych. Wielowątkowy serwer przechowujący dane odpowiada także za prawidłowe rozprowadzenie danych wśród całości użytkowników internetowych.

    Utrzymanie systemu serwerowego w ciągłym ruchu jest najbardziej skomplikowaną i kosztowną częścią projektu SETI@home. Warianty usterek sprzętu i oprogramowania są nieprzewidywalne. Dlatego architektura jest konstruowana w kierunku jak najmniejszej zależności między podsystemami. Wielowątkowy serwer można uruchomić tak, aby przy wyliczaniu pakietu do wysłania korzystał on z informacji zawartych w plikach dyskowych zamiast bazy danych, która może być wyłączona z użycia (np. awaria karty sieciowej, pamięci, procesora, płyty głównej).

    3.4.2. QMC@home

    Quantum Monte Carlo – QMC, to projekt z dziedziny chemii kwantowej. Bazuje on na metodzie Monte Carlo. Powstał w Theoretical Organic Chemistry University of Münster w Niemczech. Metoda została opracowana i pierwszy raz zastosowana przez Stanisława Ulama, uczestnika tajnych amerykańskich badań nad pierwszą bombą atomową.

    Metoda Monte Carlo jest stosowana do modelowania matematycznego zagadnień (m.in. fizyka, chemia, ekonomia, mechanika) zbyt złożonych, aby można było przewidzieć ich wyniki za pomocą podejścia analitycznego. W metodzie tej wielkości charakteryzujące proces są wybierane losowo zgodnie z rozkładem, który musi być znany.

    QMC@home został zaprojektowany w celu zastosowania metody Monte Carlo do celów chemii kwantowej. Zadaniem projektu jest testowanie, udoskonalanie i wdrażanie tej nowej, obiecującej metody.

    3.4.3. Climateprediction.net

    Climateprediction.net ma przewidywać zmiany klimatyczne zachodzące na Ziemi, jak również stworzyć lepsze, bardziej niezawodne modele matematyczne, które umożliwią dokładniejsze długoterminowe prognozowanie pogody. 26 sierpnia 2004 roku projekt Climateprediction.net został przeniesiony na platformę BOINC. Jest największym z dotychczas przeprowadzonych eksperymentów tego typu.

    Na projekt Climateprediction.net składają się trzy odrębne eksperymenty:

    • pierwszy – bada używany model
    • drugi – sprawdza jak modele odtwarzają klimat z przeszłości
    • trzeci – przedstawia prognozę klimatu dla XXI wieku

    Każdy z dystrybuowanych modeli jest używany dla wszystkich trzech eksperymentów. Poszczególne modele są autonomiczne i znacząco różnią się od pozostałych. Różne są warunki początkowe, w jakich zostały uruchomione, atrybuty wymuszających konkretny stan klimatu oraz parametry, które tworzą rzeczywisty model. Model klimatu musi posiadać pewną liczbę przybliżeń, zwanych parametryzacją. Oznacza to, że w modelu są określone liczby, które biorą pod uwagę zadane stałe wartości. Jednak wartości te nie są ściśle znane, a ich zakres jest jedynie prawdopodobny. Eksperyment bada wpływ na modelowany klimat około dwudziestu najbardziej kluczowych parametrów modelu – takich jak np. stosunek między liczbą kropel w chmurze a ilością faktycznych opadów. Niektóre kombinacje parametrów mogą odtwarzać klimat z przeszłości bardzo dobrze, ale podają znacznie odmienne prognozy na to, co może się wydarzyć w przyszłości.

    Projekt Climateprediction.net pozwala na lepsze zrozumienie działania i zmian zachodzących w tak bardzo skomplikowanym systemie jakim jest klimat globalny. Jest próbą określenia, jakie czynniki (czy generowane przez ludzkość, czy naturalne) wpływają na jego zmiany.

    3.4.4. LHC@home

    LHC@home jest projektem, który dostarcza danych umożliwiających kalibrację Wielkiego Zderzacza Hadronów – Large Hadron Collider w celu uzyskania jak najlepszej stabilności rozpędzanych wiązek cząstek. Projekt oficjalnie rozpoczęto w 50-tą rocznicę założenia CERN, tj. 29 września 2004 roku.

    Wielki Zderzacz Hadronów został zbudowany w największym na świecie laboratorium fizyki cząstek, w Europejskim Centrum Badań Jądrowych – CERN. Akcelerator cząstek został uruchomiony we wrześniu 2008 roku. Dzięki akceleratorowi naukowcy chcą odkryć nieznane dotąd cząstki, odtwarzając warunki jakie panowały we wszechświecie 13,7 mld lat temu, kilka milionowych ułamków sekundy po Wielkim Wybuchu.

    LHC zajął miejsce akceleratora zderzającego elektrony i pozytony – LEP. Główny obwód LHC zajmuje 26 659 metrowy tunel, na głębokości od 50 do 175 metrów między Jeziorem Genewskim a górami Jury, gdzie przebiega granica francusko-szwajcarska. Przyśpiesza dwie osobne wiązki protonów do energii 7 TeV (teraelektronowolt), po czym je czołowo zderza, wówczas osiągają one energię 14 TeV. Oprócz protonów akcelerator jest w stanie zderzać jony pierwiastków ciężkich (energia zderzenia nawet do 1148 TeV). Wokół czterech miejsc zderzeń wiązek w ogromnych podziemnych halach zbudowano cztery detektory dla dużych eksperymentów: ATLAS, CMS, LHCb i ALICE. Dodatkowo przy dwóch pierwszych detektorach znajdują się detektory dwóch małych eksperymentów LHCf i TOTEM, które analizują cząstki rozproszone lub produkowane pod małymi kątami.

    3.5. Aspekty praktyczne

    Przystępując do platformy BOINC można mieć słuszne wątpliwości, czy aby jest to celowe, jakie poniesiemy koszty, czy i jaki efekt będziemy z tego otrzymywać. Poprzez platformy systemów rozproszonych każdy z internautów może wspomóc badania z różnych dziedzin naukowych (medycyna, fizyka, chemia, astronomia, matematyka) poprzez użyczenie wolnej mocy obliczeniowej swojego komputera. Uczestnictwo w projekcie wymaga jedynie rejestracji, instalacji niewielkiej aplikacji oraz dostępu do Internetu. Interesujące może być to, że prowadzone komputerowe symulacje obliczeń mają odzwierciedlenie w rzeczywistości. W przypadku Folding@home symulacje komputerowe cząsteczek białka składających się w przestrzeni potwierdzono laboratoryjnie, że są praktycznie w 100% zgodne z wynikami uzyskanymi w doświadczeniach. W innym projekcie – LHC@home takie symulacje pozwalają uniknąć zniszczenia akceleratora poprzez wadliwą jego kalibrację. Uczestnictwo w projektach obliczeń rozproszonych można określić jako wolontariat w służbie nauki, której celem jest dokonanie przełomowych odkryć przy użyciu nowoczesnej technologii, co przełoży się na poprawę naszego życia w przyszłości. Owe wsparcie nauki to również możliwość sportowej rywalizacji. Organizacje prowadzące projekty naukowe, po analizie danych zwykle publikują wyniki badań na swoich stronach internetowych, tak aby były one dostępne dla każdego zainteresowanego. Osoby z takich samych projektów łączą się w zespoły, np.: FatumTech BOINC Team czy BOINC@Poland. Zespoły konkurują ze sobą w ilości obliczonych jednostek, prowadzone są statystyki i rankingi. Za udział w niektórych projektach można otrzymać certyfikat potwierdzający udział w obliczeniach [8].

    3.6. Uwarunkowania prawne

    Przed pobraniem instalacji aplikacji klienckiej BOINC napotykamy następujące zdanie: „To oprogramowanie możesz uruchomić tylko na swoim komputerze lub za zgodą właściciela komputera”. Należy się do tego bezwzględnie stosować. Regulacje oraz ustalenia prawne obowiązują wszystkich uczestników projektu.

    3.7. Podsumowanie

    Bogata literatura opisowa oraz dostępność zarówno specyfikacji projektowej jak i rezultatów tworzenia systemu BOINC pozwalają na opracowanie określonych praktycznych założeń koncepcyjnych dla wykorzystania tego systemu. Przyjęty model przetwarzania stwarza ogromne możliwości zarówno w zakresie procedur obliczeniowych jak i wielkości zbiorów danych. System BOINC jest w szerokim zakresie skalowalny zwłaszcza w obszarze parametryzowanych danych. Aktywny i czynny odzew środowiska internautów we wspomaganiu całości projektu poprzez oferowanie, a następnie praktyczne udostępnianie własnych, niewykorzystywanych mocy obliczeniowych świadczy o słuszności przyjętej koncepcji całościowej. W chwili obecnej zarówno zakres realizowanych projektów, jak i spektrum otrzymywanych wyników, wskazuje, iż tego typu podejście znajdować będzie coraz dalej idące zastosowania w rozwiązywaniu złożonych realizacyjnie oraz kosztownych obliczeniowo zagadnień natury informatycznej. Na zwrócenie uwagi zasługuje zastosowany paradygmat realizacyjny typu volunteer computing, pozwalający z jednej strony na włączenie rzeszy internautów do projektów przez wykorzystanie ich komputerów osobistych, a z drugiej strony przez aktywizację informatyczną osób zainteresowanych tego typu przetwarzaniem.

    3.8. Wykaz literatury

    1. Strona domowa projektu BOINC (dokumentacja, zasoby, pliki systemowe), U.C. Berkeley: http://boinc.berkeley.edu/, 2012
    2. Strona projektu SETI Classic (opis, cele, realizacja): http://www.boincatpoland.org/wiki/SETI_Classic, 2012
    3. Sky and Telescope, magazyn astronomiczny, strona o projekcie SETI: http://www.skyandtelescope.com/resources/seti/3304581.html, 2012
    4. SETI@home, An experiment in Public Resource Computing, U.C. Berkeley: http://setiathome.berkeley.edu/sah_papers/cacm.php, 2012
    5. Volunteer Computing for Biomedicine (strona startowa dla projektu): http://www.gpugrid.net/, 2012
    6. Validation Process in BOINC (założenia weryfikacyjne dla obliczeń): http://www.boinc-wiki.info/Validation, 2012
    7. Validation Process in BOINC (prezentacja przykładów praktycznych): http://www.boinc-wiki.info/A_Simple_Example_of_the_Validation_Process, 2012
    8. Pomierna Paulina: Projekty przetwarzania rozproszonego oparte na platformie BOINC, Praca inżynierska, Politechnika Gdańska, Wydział ETI, Gdańsk 2010