Czy udowodniono matematycznie, że program antywirusowy nie może wykryć wszystkich wirusów?

Joseph Sible-Reinstate Monica

2019-01-23 09:10:11 UTC

view on stackexchange narkive permalink

Według jednej możliwej interpretacji jest to wynikiem twierdzenia Rice'a. Program jest złośliwy, jeśli wykonuje jakąś złośliwą akcję, co czyni go właściwością semantyczną. Niektóre programy są złośliwe, a inne nie, co sprawia, że jest to nietrywialna właściwość. Tak więc, zgodnie z twierdzeniem Rice'a, w ogólnym przypadku nie można rozstrzygnąć, czy program jest złośliwy.

Komentarze nie służą do rozszerzonej dyskusji;ta rozmowa została [przeniesiona do czatu] (https://chat.stackexchange.com/rooms/88726/discussion-on-answer-by-joseph-sible-has-it-been-mathematically-proven-that-anti).

Nie wspominając o tym, że „złośliwy” to pojęcie prawie całkowicie subiektywne.Widziałem programy dezasemblujące, które były oznaczane jako złośliwe oprogramowanie, ponieważ autor antywirusów najwyraźniej uważał inżynierię wsteczną za „złośliwą” rzecz (chociaż nie przychodzi mi do głowy sytuacja, w której ktoś, kto nie chciałby tego dezasemblera na swoim komputerze, skończyłby sięsię z tym tam).

@DoktorJ: Chodzi o to, że nawet jeśli wymyślisz jakąś sztywną, nieskładniową definicję dla „złośliwego” _ (niezależnie od tego, czy w tej definicji brakuje niektórych wirusów, czy zawiera niektóre nie-wirusy) _, nadal nie można oznaczyć wszystkich / tylko złośliwychprogramy.

OP zapytał o „wirusy”, a nie złośliwe oprogramowanie.wirusy niekoniecznie są złośliwe.Jedyną właściwością determinującą jest samoreplikacja.(Teraz jest to prawdopodobnie złośliwe oprogramowanie OP _meant_ (wirus lub nie)).

@Stéphane Chazelas Samoreplikacja jest również nietrywialną własnością semantyczną, a więc jest nierozstrzygalna.

@BlueRaja-DannyPflughoeft: ważne jest, aby było to prawdą tylko o tyle, o ile nie można tego powiedzieć z góry, z gwarancją zakończenia.Biorąc pod uwagę rygorystyczną definicję działań, których program nie może wykonywać, jest to całkowicie możliwe, gdy program jest uruchomiony - taka jest zasada piaskownicy.Większość użytkowników zadowoliłaby się programem, który zatrzymuje złośliwe oprogramowanie, zanim zrobi coś złego, niezależnie od tego, czy miałby również okazję najpierw pokazać tańczące małpy.Problem w tym, że te „rygorystyczne definicje” nieuchronnie okażą się niekompletne.

Myślę, że twierdzenie Rice'a ma zastosowanie tylko wtedy, gdy musisz * z wyprzedzeniem * zdecydować, czy program jest złośliwy i jeśli nie zezwalasz na fałszywe alarmy.Jeśli skaner antywirusowy może np.przechwytywać wywołania API, modyfikować program (np. w celu wstawienia testów uruchomieniowych) i od czasu do czasu odrzucać „bezpieczny” program, powinno być możliwe udowodnienie bezpieczeństwa.W zasadzie tak np.maszyna wirtualna Java może oferować gwarancje bezpieczeństwa, prawda?

@JeroenMostert: Nie, to nie ma nic wspólnego z analizą statyczną i uruchomieniową.Różnica polega na tym, czy definicja jest semantyczna, czy syntaktyczna.„Lista działań, które program może wykonać” to definicja składniowa.Dlatego pisanie piaskownicy jest o wiele łatwiejsze niż pisanie programu antywirusowego.

@JeroenMostert: Sandboxing ** nie ** rozwiązuje problemu.Skąd wiesz, czy najnowsza wersja przeglądarki, którą zainstalowałeś, zawiera ukryte złośliwe oprogramowanie, które przechwytuje dane z klawiatury w witrynach banków?Czy zamierzasz używać innej piaskownicy dla każdej wrażliwej witryny?Skąd wiesz, że Twoje najnowsze oprogramowanie do piaskownicy samo w sobie nie jest złośliwym oprogramowaniem?Skąd wiesz, że Twój system operacyjny ...

@Joseph: Zgadzam się z twoją odpowiedzią, ale jednym z możliwych sporów jest to, że prawdziwe komputery nie są kompletne według Turinga, a zatem teoretycznie jest możliwe (choć praktycznie niemożliwe) ustalenie, czy jakikolwiek program spowodowałby wejście twojego konkretnego komputera w niepożądany stan.Oczywiście nie byłbyś w stanie tego zrobić w samym komputerze, ale teoretycznie możesz użyć innego komputera, który ma więcej pamięci, aby przeprowadzić analizę.Oczywiście potrzebny czas jest proporcjonalny do liczby możliwych stanów, w których może znajdować się komputer ...

@user21820: Nigdy nie powiedziałem, że piaskownica jest lub może być idealnym rozwiązaniem (powinno być całkiem oczywiste, że rozwiązanie * no * może być absolutną ochroną przed złośliwym oprogramowaniem, z prostego praktycznego punktu widzenia, nie mówiąc już o teorii).Pytanie brzmi, czy twierdzenie Rice'a jest słuszne, aby przywołać tutaj matematyczny dowód, że takiego złośliwego oprogramowania nie można wykryć.(Lub przechodząc o jeden poziom wyżej, jeśli Schneider w ogóle odnosił się do tego, co nie wydaje się mieć miejsca - pomimo niedostatecznej uwagi, [ta odpowiedź] (https://security.stackexchange.com/a/202003/ 147318) wydaje się być właściwym).

@user21820, który nie jest nawet kompletny, ponieważ dwa programy mogą różnić się tylko tym, gdzie faktycznie wysyłane są dane.Aplikacja bankowa i wykrywacz haseł odczytują Twoje hasło i wyślą je na serwer - Twój komputer zrobi dokładnie to samo, ale odbiorca jest inny - więc lokalne skanowanie nigdy nie może zdecydować, czy odbiorca jest osobą, której faktycznie zamierzaszwysłał twoje dane do, więc cały internet ze wszystkimi osiągalnymi maszynami powinien być minimalnie twoim automatem stanowym do sprawdzania wszystkich stanów - powodzenia ...

@Falco: Tak, oczywiście.Jest wiele takich szczegółów, ale pole komentarza było zbyt płytkie, aby je zawierać.

walen

2019-01-23 20:21:11 UTC

view on stackexchange narkive permalink

Prawdę mówiąc, można łatwo udowodnić coś przeciwnego : ponieważ wszystkie wirusy komputerowe są w taki czy inny sposób kodem wykonywalnym, wszystko, co musisz zrobić, to napisać program antywirusowy, który zgłosi KAŻDY plik wykonywalny kod jako wirusowy. Wynika z tego logicznie, że taki program wykryje WSZYSTKIE możliwe wirusy :

Cały kod jest wykrywany przez program antywirusowy (C → D)
Wszystkie wirusy to kod (V → C)
Wszystkie wirusy są wykrywane przez Twój program antywirusowy (V → D)

Jasne, można argumentować, że to oprogramowanie antywirusowe odrzuca zbyt wiele „fałszywe alarmy”. Ale jakie są kryteria decydujące o tym, czy pozytyw jest fałszywy, czy prawdziwy? Ach! Okazuje się, że rozróżnienie między łagodnym kodem a złośliwym kodem, między uczciwym pakietem do „zdalnego sterowania komputerem” a trojanem takim jak Netbus jest całkowicie arbitralne, więc całe pytanie jest bezcelowe.

Uroczy.To znaczy całkowicie nieistotne, ale także urocze i sprytne.

Nieco bardziej pożytecznie można wymagać, aby programy składały się z pewnych działań, których nie można skomponować w taki sposób, aby wywoływały zachowanie „wirusowe”, a następnie odrzucać programy, które nie składają się wyłącznie z takich działań.Takie podejście jest praktyczne do wielu celów;Największym problemem jest to, że zakres zadań, które można wykonać przy użyciu tylko działań, które nie mogą wywołać zachowania wirusa, jest nieco mniejszy niż zakres zadań, które ludzie oczekują od komputerów.

@supercat, problem z twoją wersją polega na tym, że musisz wymyślić definicję „zachowania wirusa”, którą można zastosować programowo.Na przykład kopacz bitcoinów w Javascript może być podobny do wirusa, gdy odwiedza witrynę New York Times, ale jest pożądanym zachowaniem, gdy odwiedza Joe's Discount Pirate Software.Szyfrowanie zawartości dysku twardego może być dobrym zachowaniem, gdy robi to oprogramowanie FDE, i podobne do wirusa, gdy robi to ransomware.

Ten program antywirusowy wykryłby * siebie * jako wirusa i zamknąłby się, uniemożliwiając wykrycie czegokolwiek innego.

@Mark: Zdefiniowałbym wirusa jako program, który instaluje się samoczynnie bez zgody właściciela komputera lub operatora.Jeśli zestaw dopuszczalnych działań nie obejmuje żadnych środków umożliwiających automatyczne uruchomienie programu, nie będzie możliwe zbudowanie wirusa z działań z tego zestawu.

@supercat Wiele wirusów jest instalowanych za zgodą operatora, ale robią rzeczy, na które operator nie wyraził zgody.Jeśli jednak zapobiegniesz automatycznemu uruchamianiu, ponowne uruchomienie go zabije, ale nie skutki uboczne.

@Poik: Nie wszystkie złośliwe programy, które się rozprzestrzeniają, są wirusami.Aby fragment kodu był wirusem, musi on między innymi móc, bez zgody operatora, spowodować wykonanie się w przyszłości, gdy żadna jego część nie jest uruchomiona.Uniemożliwienie aplikacjom modyfikowania innych programów lub kolejności startowej w 100% zapobiegnie wirusom, chociaż inne formy złośliwego oprogramowania, takie jak robaki, nadal byłyby możliwe.

poza tym, jak rozpoznajesz, czy coś jest kodem wykonywalnym?np. wirus JPG, który wykorzystywał błąd w renderowaniu JPG firmy Microsoft (powodując wykonanie kodu, gdy Microsoft Internet Explorer odwiedził stronę internetową).Więc jedynym sposobem byłoby rozwinięcie pseudokodu, aby powiedzieć, że wszystkie bity są, ponieważ każdy bit może być kodem wykonywalnym.Jeśli mamy być tak niedorzeczni, mogę powiedzieć, że „bajty” (zgłaszane przez „dir”) są w rzeczywistości tłumaczeniem „znalezionego wirusa”, więc „dir” to w rzeczywistości oprogramowanie antywirusowe, które to robi.Całkowicie śmieszne.(Nie znaczy to, że nie doceniam śmieszności. Brawo.)

Program antywirusowy, który wykrywa cały kod wykonywalny jako złośliwy, wykryłby również system operacyjny, na którym działa, jako złośliwy.Gdyby ten program antywirusowy faktycznie coś z tym zrobił, za każdym razem dość szybko zawiesiłby system operacyjny.Nie byłby świetnym programem antywirusowym, ale zrobiłby paskudnego wirusa.

Brzmi jak argument przemawiający za * białą listą * tylko poszukiwanych programów, jak w repozytorium tylko przetestowanego oprogramowania do zainstalowania (może nawet FOSS, podobnie jak większość repozytoriów Linuksa), aby przynajmniej uniknąć celowego instalowania złośliwych rzeczy

Zadając pytanie o coś choćby zdalnie praktycznego, można założyć, że trywialne rozwiązanie jest domyślnie wykluczone.

Sprzeciwiłbym się pierwszemu założeniu: * Cały kod jest wykrywany przez Twój program antywirusowy. * Jako część tego, co jest praktycznie niemożliwe.

@Xen2050 "Brzmi jak argument przemawiający za umieszczeniem tylko na białej liście poszukiwanych programów ..." Tak, rzeczywiście.Niestety istnieją na przykład miliony aplikacji na smartfony.Nie chcę być tym, który musi ich wszystkich testować.

Czy można uważać skrypt za „kod”?Jeśli tak, myślę, że pierwsza przesłanka staje się nieco mniej trywialna

Co oznacza Virical?Nie mogę znaleźć na to definicji.

@TemporalWolf Nie, to jest bolesne: pierwsza instrukcja kodu maszynowego jest zatrzymana.Jeśli w dowolnym momencie zauważysz, że twoja maszyna została zatrzymana, oznacza to, że wykryła kod.

-1, ponieważ ta odpowiedź w żaden sposób nie jest pomocna.

@TOOGAM: dokładnie.Jeśli mówimy o x86, większość sekwencji bajtów dekoduje się jako prawidłowe instrukcje x86.Zwykle tekst ASCII daje w wyniku sekwencję instrukcji, która nie ma żadnego sensu lub zawiera instrukcje uprzywilejowane, takie jak „6c ins” i „6e out”, ale nierzadko sekwencja nie zawiera instrukcji niedozwolonych.(Szczególnie w trybie 32-bitowym.) Umieściłem tekst tej odpowiedzi wewnątrz `.ascii" ... "` w foo.s (zastępując znaki nowej linii przez `\ n` i unikając cudzysłowów) i składałem go za pomocą` gcc-m32 -c foo.s`.Wiele krótkich instrukcji rozgałęzień warunkowych, ale żadnych instrukcji nielegalnych!

Och, mogę umieścić to na Godbolt w sposób, który pokaże demontaż * z * hexdump: https://godbolt.org/z/IIXBUc (w przeciwieństwie do tej pierwszej próby lang = asm, która nie: https: // godbolt.org / z / -2ATIj).Niektóre z zabawnych dłuższych instrukcji obejmują `imul esi, DWORD PTR [edx + esi * 2 + 0x61], 0x202c7972`.

@Fax, który zakłada, że możesz rozpocząć skanowanie programu.Być może jest uruchamiany przez podłączone urządzenie peryferyjne, działa jako program ładujący, odszyfrowywany na żądanie lub naśladuje interakcję użytkownika, udając klawiaturę.Wszystkie cztery z nich wymagają różnych, nietrywialnych podejść do egzekwowania i są to wszystkie rzeczy, o których obecnie wiadomo, że są wykorzystywane na wolności.Twój system wymaga również absolutnego, nietrywialnego ograniczenia, że żadne niewykonywalne pliki nie zawierają binarnej reprezentacji instrukcji zatrzymania maszyny ... oto kilka znaków Unicode, które zawierają 0xF4, kod x86: ôǴ˴ϴӴ ״

@TemporalWolf Nie, nie zakłada tego.Z perspektywy programu „obecny jest dowolny kod” jest logiczną tautologią.Nikt nie powiedział, że komputer nie może być doskonałym przyciskiem do papieru.

@JackAidley Nie ma tam nic „mądrego”.To tak, jakbyśmy stwierdzili, że jeśli się zabijemy, nie będziemy mieli więcej problemów w życiu.

Ta odpowiedź działałaby idealnie w konfiguracji, w której AV jest wezwany do oceny fragmentu kodu i musi udzielić odpowiedzi.Niestety pozostawia to lukę w dowodzie, ponieważ musiałbyś udowodnić, że AV zostanie poproszony o ocenę każdego bitu kodu.(I mniejszą lukę, na którą musi być w stanie odpowiedzieć).

Mam lekarstwo na każdą chorobę znaną człowiekowi!

Wydaje mi się, że jest to nieprawidłowe użycie wyrażenia „wykryj”.Jest to analogiczne do stwierdzenia, że jeśli ława przysięgłych uzna człowieka winnego z niewłaściwych powodów, nawet jeśli był on naprawdę winny, to oni * wiedzieli *, że jest winny.* Wiedzieć * oznacza coś więcej niż tylko zdarzenie, aby być poprawnym, a „wykryć” jest tutaj używane bardzo podobnie;to coś więcej niż tylko decydowanie.Powinno to oznaczać, że została przeprowadzona pewna analiza i istnieje uzasadnienie takiej decyzji.

@Steve Wygląda na niepoprawną próbę przekształcenia słowa „wirus” w przymiotnik.Jeśli tak, powinien być „wirusowy”.

@jpmc26 Bardziej jak obcy błąd.Wiem, że po angielsku jest to „wirusowe”, ale po hiszpańsku to „vírico, vírica” i niechcący je wymieszałem.

Harry Johnston

2019-01-23 12:20:05 UTC

view on stackexchange narkive permalink

Według Wikipedii:

W 1987 Fred Cohen opublikował demonstrację, że nie ma algorytmu, który byłby w stanie doskonale wykryć wszystkie możliwe wirusy.

Odwołuje się również do tego dokumentu. To może być analiza, do której odnosił się pan Schneier.

Schneier stwierdza tutaj, że jest to wynik, do którego odnosił się, gdy wygłosił bardzo podobne oświadczenie jakiś czas później w innym kontekście: https://www.schneier.com/blog/archives/2009/07/making_an_opera.html

@Stephan: Dla każdego możliwego pliku binarnego istnieje hipotetyczna platforma, dla której jest on zjadliwy i hipotetyczna platforma, dla której nie jest zjadliwy.To twierdzenie jest silniejsze niż twierdzenie Rice'a, ponieważ odnosi się również do hiperkomputerów.

więc udowodniono, że w 1987 roku doskonały program antywirusowy nie istniał?schludny.ale czy udowodnił również, że nie można stworzyć idealnego programu antywirusowego, czy po prostu nie istniał od 1987 roku?

@user1067003, Nie jestem informatykiem, ale jestem prawie pewien, że wyrażenie „nie ma algorytmu” oznacza, że nie ma żadnego możliwego algorytmu, a nie tylko, że nie ma * znanego * algorytmu.Inaczej nie byłby to bardzo interesujący wynik.(Dowód, jak napisano, prawdopodobnie dotyczy tylko klasycznych komputerów, może być konieczne przerobienie go, aby objąć komputery kwantowe lub inne, bardziej zawiłe architektury).

Ta odpowiedź w dużej mierze opiera się na zewnętrznym łączu, aby odpowiedzieć na pytanie.Czy możesz podsumować argumenty z tego artykułu?

Komputery kwantowe @HarryJohnston: są równoważne maszynom Turinga pod względem obliczalności, więc nie, nie trzeba ich przerabiać.W rzeczywistości prawie każdy informatyk uważa, że _ każdy_ komputer możliwy do fizycznej realizacji jest w najlepszym przypadku [odpowiednikiem Maszyny Turinga] (https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis)

@BlueRaja-DannyPflughoeft w tezie kościoła stwierdza, że ludzki umysł jest odpowiednikiem maszyny Turinga.Nie ma przy tym żadnej podstawy do tego, czy hiperkomputer można skonstruować, czy nie.Oznacza to jedynie, że nie bylibyśmy w stanie wykonać obliczeń ręcznie.Musielibyśmy polegać na poprawności maszyny.Jak ten artykuł w ogóle potwierdza to twierdzenie?

Michael Kay

2019-01-24 00:24:46 UTC

view on stackexchange narkive permalink

Stwierdzenia nie można udowodnić matematycznie, chyba że zostanie przeformułowane jako twierdzenie matematyczne.

Co najmniej wymaga to matematycznie poprawnej definicji tego, czym jest „wirus”: co jest wyzwaniem; i możesz skończyć z abstrakcją, która nie jest przydatna w praktyce, ponieważ obejmuje pewne zachowania, które ludzie uważają za całkowicie łagodne i przydatne, i / lub wyklucza niektóre zachowania, które ludzie uważają za antyspołeczne.

Trudne Rzecz w tym, że wirus to program, który w jakiś sposób zmienia swoje środowisko, a każda próba rygorystycznego zdefiniowania środowiska będzie zbyt ograniczająca dla praktycznego zastosowania.

Więc powiedziałbym nie: propozycja nie można tego matematycznie udowodnić, a to dlatego, że nie można tego sformułować matematycznie.

Kontrprzykład: Specjalizuję się w oryginalnym pytaniu (tracąc ogólność), definiując * wirusa * jako dowolny `skrypt bash`, który wywołuje` rm -rf / * `, gdy jest uruchamiany bez argumentów;i zdefiniuję * antywirus * jako wersję interpretera bash, który uniemożliwia wykonanie polecenia `rm -rf / *`.Mam nadzieję, że zgodzisz się, że możemy przejść całą drogę w dół, rygorystycznie definiując, co „interpreter bash”, „wykonaj” itp. Oznacza matematycznie.Czy właśnie sformułowałem słabszą wersję pierwotnego pytania?Czy to obala twoje twierdzenie, że * nie można tego sformułować matematycznie *?Tak i tak.

@ulidtko Nie. Nie możesz po prostu arbitralnie zdefiniować wirusa jako cokolwiek chcesz.W przeciwnym razie mógłbym zdefiniować wirusa jako „oprogramowanie, które ma w nazwie„ antywirus ””, co nie pomogłoby w żadnej dyskusji, ponieważ jest to dyskusja o filozofii, a nie o bezpieczeństwie czy matematyce.W rzeczywistości twoja definicja wirusa jest taka, jak powiedzenie „Zdefiniowałem zbiór liczb parzystych jako {2}”.Śmiało, stwórz taki system, jeśli chcesz, ale niczego nie zaprzeczyłeś, robiąc to.Jak zasugerował Michael, „wirusa” nie można zdefiniować matematycznie w żaden sposób przydatny w tej rozmowie.

Odp: „Wymaga to przynajmniej matematycznie poprawnej definicji tego, czym jest„ wirus ””: Niekoniecznie.Jeśli istnieją cechy, które miałyby zastosowanie do * dowolnej * definicji „wirusa”, możesz być w stanie matematycznie sformalizować niektóre z nich bez konieczności tworzenia konkretnej, pełnej definicji.Ta częściowa charakterystyka mogłaby wystarczyć do zastosowania [twierdzenia Rice'a] (https://en.wikipedia.org/wiki/Rice%27s_theorem).

@ulidtko Na tej samej podstawie mógłbym zdefiniować wirusa jako dowolny program wysyłający e-mail.Jestem pewien, że mógłbym zrobić jakieś rozumowanie na temat tej klasy programów, ale nie powiedziałoby mi to nic o klasie programów, które zwykli ludzie klasyfikują jako wirusy w prawdziwym świecie.

@ruakh Twierdzenie Rice'a ma zastosowanie tylko wtedy, gdy ograniczysz program antywirusowy do działania poprzez statyczną analizę kodu (źródłowego lub obiektowego).Pytanie dotyczy „wykrywania wirusów”, a nie tylko wykrywania ich za pomocą analizy statycznej.Co się stanie, jeśli wykryjesz je, obserwując ich samoreplikację?

@MichaelKay: Jestem świadomy;Wspomniałem tylko o twierdzeniu Rice'a jako o przykładzie, dlaczego twoje stwierdzenie było błędne.Przepraszam, jeśli to było niejasne.

W systemie 64-bitowym z pełną 64-bitową przestrzenią pamięci i bez pamięci rozszerzalnej rozmiar pamięci wyniesie 2 $ ^ {64} $ bajtów.Jeśli następnie weźmiemy pod uwagę wszystkie możliwe permutacje tej przestrzeni pamięci, wówczas w tej przestrzeni pamięci znajduje się 8 $ ^ {2 ^ {64}} $ programów.Mniej, jeśli weźmiemy pod uwagę, że skompilowany plik binarny będzie współistniał z pamięcią.Ponieważ liczba programów jest ograniczona, można je podzielić na zbiór szkodliwych programów i niezłośliwych programów.Taka byłaby definicja złośliwych programów 64-bitowych.Twoje twierdzenie jest takie, że nie mamy definicji, która rozszerzyłaby się do 128 bitów i tak dalej.

Twoje twierdzenie może również dotyczyć tego, że jedna konkretna kombinacja bitów może być złośliwa dla jednego użytkownika i niezłośliwa dla innego użytkownika.W takiej sytuacji problem można rozwiązać, zezwalając użytkownikowi na umieszczenie na białej liście czegoś, co zostało oznaczone jako złośliwe.Nie jest to idealne rozwiązanie, ale tak naprawdę oznacza to, że ludzie będą mieć różne definicje złośliwego oprogramowania lub w bardziej realistycznym znaczeniu - że niektórzy użytkownicy * chcą * uruchamiać złośliwy kod na ich własnej maszynie.

Nat

2019-01-25 11:00:19 UTC

view on stackexchange narkive permalink

tl; dr - odpowiedź zależy od dokładnie tego, jakie wymagania stawiasz przed pytaniem.

Jeśli po prostu chcesz wykryć wszystkie wirusy bez dalszych ograniczeń, a następnie oznacz wszystko jako wirus i gotowe.
Jeśli chcesz poprawnie zidentyfikować wszystkie programy jako wirus czy nie, to jest to niemożliwe w przypadku niezwiązanym, ponieważ problem klasyfikacji ogranicza się do problemu zatrzymania.
Jeśli chcesz poprawnie zidentyfikować wszystkie programy jako wirusy lub nie, i rozważasz maszynę skończoną, wtedy jest to teoretycznie możliwe, ale nie jest to generalnie wykonalne w praktyce.
Jeśli pozwolisz, że komputer może generować przypadkowe błędy, to każdy program może być wirus.

Przypadek 1: Pełne wykrywanie wirusów

Oczywiście oznaczanie wszystkich programów jako wirusów wyłapuje je wszystkie. ( Pok'e'mon! )

Zaczynając od tego przypadku, aby zwrócić uwagę, że nie jest trudno wykryć wszystkie wirusy; raczej konkretnym problemem teoretycznym jest prawidłowe klasyfikowanie programów iff jako wirusów.

Przypadek 2: Niemożliwe jest poprawne sklasyfikowanie w ogólnym, nieograniczonym scenariuszu

Rozważmy program:

  doHaltingProblem (); // Sama operacja nie jest wiruseminstallEveryVirusEver (); // Zdecydowanie operacja wirusa, ale czy to się stanie?

W tym przypadku program jest wirusem tylko wtedy, gdy problem z zatrzymaniem zatrzyma się, pozwalając installEveryVirusEver () . Tak więc wykrywanie wirusów ogranicza się do problemu zatrzymania w ogólnym, niepowiązanym przypadku.

Przypadek 3: Możliwe przez brutalne wyszukiwanie w ograniczonych scenariuszach

Jeśli programy mają być klasyfikowane jako wirusy -lub-nie mają działać na maszynie skończonej, możesz po prostu zasymulować pracę maszyny z każdego możliwego stanu początkowego. Maszyny skończone w końcu zapętlą się z powrotem do poprzedniego stanu, więc z konieczności jest to analiza skończona (jeśli długa).

Przypadek 4: Na komputerach, na których mogą występować błędy, wirusy mogą pojawiać się spontanicznie

Zakładając, że na komputerze można uruchomić program, który zostałby uznany za wirusa, i istnieje niezerowa szansa na losowe przesunięcie mutacji w ten stan, a następnie powinien ostatecznie dojść do stanu wirusa.

Co jest trochę nudne, ale tylko dla zachowania kompletności.

Dyskusja na temat cytat w pytaniu

Wirusy nie mają „lekarstwa”. Udowodniono matematycznie, że zawsze można napisać wirusa, którego żaden istniejący program antywirusowy nie może zatrzymać.

- „ Sekrety & Lies ” , Bruce Schneier, strona 154

Jak wskazano w powyższym przykładzie (1), możliwe jest oznaczenie wszystkich wirusów po prostu oznaczając wszystko jako wirus; to łatwe. Niemożliwe jest, w przypadku niezwiązanego, określenie, czy każdy możliwy program jest wirusem, czy nie.

Ponadto trudno jest ustalić, czy określone programy są wirusami w przypadkach powiązanych. Na przykład rozważmy program:

  var toExecute = decryptByBruteForce ([szyfrogram]); // Odszyfruj następną część programu przez brute-forcerun (toExecute); // Uruchom teraz odszyfrowaną część programu

Jak omówiono w przypadku (3), ten program można sklasyfikować jako wirus lub nie, gdy jest uruchamiany na skończonej maszynie, ale ponieważ wymagałoby to brutalnego wymuszenia zaszyfrowanej wiadomości, jest to raczej mało wykonalne w praktycznych scenariuszach.

Dlatego w rzeczywistych aplikacjach sprowadza się to do problemu heurystyki: programy antywirusowe odgadują, co jest wirusem, a co nie. Lub jeśli chcesz bardziej niezawodnych zabezpieczeń, możesz mieć program antywirusowy oznaczający wszystko, czego nie może udowodnić, że jest bezpieczny, unikając konieczności klasyfikowania każdego możliwego programu.

Niestety, użycie heurystyki stwarza dobrze znanym napastnikom luki w zabezpieczeniach. Bez czytania źródła cytatu podejrzewam, że właśnie do tego problemu próbowali się odnosić.

Przypadek (4) jest nie tylko nudny, ale wskazuje na bardziej prawdopodobny scenariusz i scenariusz problematyczny.Rozważmy kod, który zawiera wywołania if (cannotHappen) installEveryVirusEver ();where cannotHappen nie może się zdarzyć, jeśli maszyna działa poprawnie, ale może się zdarzyć, jeśli maszyna jest przetaktowana.Jak to poprawnie zaklasyfikować?

@HansOlsson Tak, wymagałoby to uogólnienia ontologii, aby uchwycić problemy, które nie pasują dobrze do modelu deterministycznego;przypuszczalnie musielibyśmy rozważyć zbiór możliwych wyników, a następnie sklasyfikować je według tego, jak bezpieczne byśmy je uznali, albo po prostu przyznać, że programy ogólnie mogą działać złośliwie, nawet jeśli nie zostały do tego zaprojektowane.Miałem nadzieję, że ukłonię się w kwestiach takich jak [młotek do wiercenia] (https://en.wikipedia.org/wiki/Row_hammer), gdzie założenie bezbłędnego działania może naprawdę zepsuć analizę.

„brutalne wymuszanie zaszyfrowanej wiadomości” Dlaczego nie uruchomić programu w piaskownicy i dowiedzieć się, jak odszyfrowuje on samą wiadomość?IIRC tak już działa niektóre programy antywirusowe.

@micsthepick Uruchamianie programu w piaskownicy jest rozwiązaniem o lepszym skalowaniu, które może być ogólnie lepsze w nietrywialnych przypadkach, więc masz rację, że byłoby to preferowane w praktyce.Po prostu pytanie dotyczy antywirusa w sensie analizy zapobiegawczej;sandboxing to inny temat.

Warto zauważyć, że przykład problemu z zatrzymaniem można obejść, po prostu oznaczając dowolny program, który może zainstalować wirusa, jako wirusa (tj. Dedykowany do tego kod bajtowy, który istnieje, więc prawdopodobnie oprogramowanie może to zrobić).

James_pic

2019-01-23 23:03:48 UTC

view on stackexchange narkive permalink

To zależy od Twojej definicji „zatrzymania”.

Jeśli zdefiniujesz zatrzymanie jako „wykrycie z wyprzedzeniem, że kod może zrobić coś złośliwego i uniemożliwić jego uruchomienie”, to tak jak inni wspomniano, jest to niemożliwe zgodnie z twierdzeniem Rice'a.

Jeśli zdefiniujesz zatrzymanie jako „wykryj, kiedy uruchomiony program próbuje zrobić coś złego, a następnie zatrzymaj to”, to twierdzenie Rice'a nie ma zastosowania. Twój program antywirusowy nie musi decydować, czy program może zrobić coś złośliwego, tylko czy robi teraz coś złośliwego.

AFAIK, druga wersja nie została matematycznie niemożliwa. I rzeczywiście, dla każdej wystarczająco szczegółowej definicji „złośliwego” jest to bardzo wykonalne - jest to zasadniczo piaskownica.

Wydaje się jednak prawdopodobne, że nie ma dobrej definicji „złośliwego”, która obejmowałaby wszystko formy złośliwości, które może podejmować wirus. A co z wirusem, który wydobywa bitcoiny? A może to serwuje pirackie filmy? Albo że spamuje fora dyskusyjne w Twoim imieniu? Wszystkie te są nie do odróżnienia od kodu uruchamianego przez użytkowników, którzy naprawdę chcą robić dokładnie te rzeczy. W związku z tym podejrzewam (chociaż nie znam żadnej próby udowodnienia), że tworzenie programu antywirusowego jest kompletne.

Problem z definiowaniem złośliwego oprogramowania nie jest niczym złym.Różni ludzie mają różne zainteresowania związane z budowaniem odpowiedniej dla nich definicji, ale to w porządku.

Tak więc ktoś tworzy łącze w witrynie internetowej, która instaluje oprogramowanie na komputerze w celu monitorowania oglądanych filmów i przekazuje dane do MegaCorp.Czy to wirus?Czy Twoja odpowiedź różni się w zależności od tego, czy „kimś” jest Microsoft, czy nastoletnim hakerem?Czy Twoja ocena matematyczna oprogramowania uwzględnia wiarygodność twórcy?Krótko mówiąc, czy można to właściwie sformułować jako problem matematyczny?

@MichaelKay: Tak.Nie. Nie, tylko czy to działanie narusza Twoje zasady.Tak.

Słyszałem o NP Complete, ale co to jest AI kompletne?

Konkurencja @Michael AI to (moim zdaniem nieco bardziej wełnista definicja) idea, że „nie można rozwiązać tego problemu bez stworzenia sztucznej inteligencji ogólnej”.Myślę, że nie jest tak jasno zdefiniowany jak NP, więc prawdopodobnie nie podlega dowodowi matematycznemu.

@R Rosnące wyrafinowanie złośliwego oprogramowania i rosnąca głupota komercyjnych dostawców oprogramowania sprawiają, że ta szara strefa jest bardzo duża.Najbardziej sensowną definicją złośliwego oprogramowania byłoby dla mnie oprogramowanie, które zrobiło coś, czego użytkownik nie chciał i nie był tego świadomy - co zależy nie tylko od pragnień użytkownika, ale także od jego zdolności zrozumienia, co się dzieje.Czy obejmuje to kiepski pasek narzędzi przeglądarki, który Oracle dołącza do aktualizacji Java?A może serwer proxy MITM Lenovo dołączony do niektórych laptopów?Prawie wszystko oprócz GNU HURD znajduje się w szarej strefie.

Dzięki, to ma sens.Słyszałem mniej rygorystyczną wersję tego, na przykład: oto pięć (lub 10) problemów, które miałyby dużą wartość do rozwiązania, ale okazuje się, że rozwiązanie tylko jednego z nich (utworzenie AGI / ASI) faktyczniezapewnić środki do rozwiązania również innych (zakładając, że to nas nie zniszczy / nie uczyni nas swoimi zwierzętami domowymi / itp.)

Przypomina mi stare pytanie „co to jest chwast?”z odpowiedzią „wszystko, czego nie chcesz, aby rosło w Twoim ogrodzie”, re: Twój komentarz do @R

Michał Kuliński

2019-01-23 17:35:02 UTC

view on stackexchange narkive permalink

Tak, zostało to matematycznie udowodnione przez Alonzo Church w latach 1935–36, a wkrótce potem przez Alana Turinga w 1936 roku.

https://en.wikipedia.org/wiki/Entscheidungsproblem

Gdyby stwierdzenie * dało się * w jakiś sposób zredukować do problemu zatrzymania, interesujące byłoby pokazanie, że tak jest, a nie tylko porzucenie tego.Lub, mówiąc bardziej bezpośrednio: nie, zdecydowanie nie to udowodnili Church i Turing (nie jest to nawet bliskie temu, co zamierzali udowodnić).

Tak, @JeroenMostert masz rację.Myliłem się.Church i Turing udowodnili, że nie ma mechanizmu, który decydowałby, czy taki program wykrywający wszystkie wirusy można w ogóle napisać.Pomieszałem pojęcia.Wujek Bob pisał o tym na blogu: https: //blog.cleancoder.com/uncle-bob/2018/06/21/IntegersAndEstimates.html

Czy więc tę odpowiedź należy usunąć lub całkowicie przepisać?

Blog Martina, choć zabawny, popełnia niektóre z bardziej powszechnych błędów, jeśli chodzi o wyjaśnienie problemu zatrzymania.Na przykład „specyfikacja programu jest wielkim, dużym równaniem diofantynowym pośród miliardów niewiadomych” jest błędne, jasne i proste.Z pewnością jest to * a * sposób określania programu (jeśli mrużysz oczy), ale musisz być * o wiele * bardziej ostrożny, aby sformułować sensowne stwierdzenia na temat tego, co mówią dowody, a które nie są możliwe.Wyjaśnienia takie jak te mają tendencję do zaciemniania, a nie wyjaśniania - rzeczywista matematyka jest subtelna, ale nie bez powodu, te rzeczy * są * subtelne.

Nie jestem pewien, czy ta odpowiedź jest błędna: jeśli „zatrzymać” oznacza „wygenerować raport zawierający listę wszystkich wirusów w systemie, nie więcej ani mniej”, to nie możemy z góry udowodnić, że program zatrzyma się zpoprawna odpowiedź, chyba że uruchomimy ją, aby się dowiedzieć.Należy zauważyć, że wspomniany artykuł odnosi się również do problemu zatrzymania: https://web.archive.org/web/20140525233117/http://grnlight.net/index.php/computer-articles/109-an-undetectable-computer-wirus

Usunięto @schroeder.

@stevegt problem zatrzymania nie polega na tym, czy da poprawną odpowiedź.Chodzi o to, czy w ogóle może się zatrzymać, co jest okresem bez odpowiedzi.Nigdy nie dowiesz się, czy się zatrzyma, ale nie jest to przydatne, ponieważ nie nawiązano połączenia między maszyną wykrywającą zatrzymanie maszyny a maszyną wykrywającą, czy maszyna robi coś złośliwego.

Philipp

2019-01-25 14:58:42 UTC

view on stackexchange narkive permalink

Nie, nie możesz, ponieważ różnica między złośliwym oprogramowaniem a użytecznym programem jest całkowicie subiektywna. Każde „złe” zachowanie może być zachowaniem zamierzonym. Na przykład mam teraz uruchomione na komputerze następujące programy:

Program, który szyfruje wszystkie moje pliki. Czy jest to ransomware cryptolocker czy narzędzie do szyfrowania całego dysku?
Program, który umożliwia zdalny dostęp do kontroli mojego komputera. Czy to trojan, czy może Team Viewer?
Program, który tworzy połączenia sieciowe ze wszystkimi rodzajami komputerów w całym Internecie i wymienia z nimi niejasne dane. Czy to botnet czy rozproszona platforma komputerowa?
Program, który wysyła wszystkie moje pliki osobiste na zdalny serwer. Czy to oprogramowanie szpiegowskie czy kopia zapasowa w chmurze?
Program, który pobiera pliki wykonywalne z Internetu i je uruchamia. Czy to dropper złośliwego oprogramowania, czy Steam?

Nie możesz odróżnić różnicy, ponieważ z czysto technicznego punktu widzenia robią dokładnie to samo. Jedyna różnica polega na zamiarze. Jeden program oszukuje użytkownika co do tego, co robi i działa wbrew jego interesom, drugi robi dokładnie to, czego oczekuje użytkownik. Ale to, czego użytkownik naprawdę chce od swojego oprogramowania, to coś, czego maszyna nie może zdecydować ... przynajmniej nie na obecnym etapie technologii AI. Dlatego wszystkie skanery antywirusowe są głównie oparte na sygnaturach.

kajacx

2019-01-24 18:43:56 UTC

view on stackexchange narkive permalink

Aby matematycznie udowodnić, że zawsze można napisać wirusa, który może ominąć wszystkie istniejące programy antywirusowe, musisz najpierw matematycznie zdefiniować, co to jest wirus, i powodzenia.

Może „program, który wykonuje niepożądane działania”? Cóż, to po prostu niemożliwe, wyobraź sobie program, który otwiera połączenie z twoim komputerem i umożliwia zdalne sterowanie. Program antywirusowy widzi, że program to robi, ale skąd może wiedzieć, czy jest to pożądane, czy nie?

Może to być legalny program do zdalnego sterowania, taki jak TeamViewer, lub może to być wirus udający prosty program do przeglądania obrazów, co najmniej tak, Twój program antywirusowy zobaczy program, który może odczytywać i wyświetlać obrazy z komputera oraz otwierać połączenia zdalne, i nie będzie mógł stwierdzić, czy jest to „pożądane” zachowanie, czy nie, ponieważ nie może wiesz, dlaczego instalujesz ten program.

Matthew

2019-01-25 17:45:32 UTC

view on stackexchange narkive permalink

Jak wskazał @walen, w rzeczywistości możliwe jest wykrycie wszystkich wirusów, jeśli dozwolone są fałszywe alarmy: po prostu zgłoś wszystko jako wirusa.

Załóżmy, że możliwe jest również wykrycie wszystkich wirusów jeśli fałszywe alarmy nie są dozwolone. Będziemy mieć funkcję IsVirus , którą można uruchomić na dowolnym programie i zwracać, czy jest to wirus, czy nie. Teraz rozważmy program, który nazwiemy P:

  if IsVirus (P): exitelse: DoVirusThings

Co jest wartością IsVirus (P) ? Jeśli jest to true , to P po prostu kończy pracę, nic nie robiąc, i dlatego mamy fałszywie dodatni wynik. Ale jeśli jest false , to P robi wirusy i mamy niewykrytego wirusa.

Dowodzi to, że nie jest możliwe wykrycie wszystkich wirusów, jeśli fałszywe alarmy nie są dozwolone.

Głosujący, proszę wyjaśnić dlaczego.O ile wiem, ten dowód jest ważny.

Nie głosowałem przeciw, choć wygląda to trochę dziwnie, ponieważ wydaje się, że nie ma sprzeczności.To znaczy, jeśli `IsVirus (P)` jest prawdą, to twój skrypt nie jest wirusowy;jednakże `IsVirus (P)` twierdził, że `P` był wirusowy, a nie Twój skrypt.

Realistycznie, nikogo nie obchodzi, gdyby `IsVirus` zgłosił, że` P` jest rzeczywiście wirusem, nawet jeśli w rzeczywistości nie byłby nim z taką definicją `P`.Rzeczywiście, nie jest wcale nierozsądne * nazywać * `P` wirusem, ponieważ jest on zaprojektowany do robienia złych rzeczy i sprytny z nami, jeśli spróbujemy go zidentyfikować.Innymi słowy, samo wywołanie „IsVirus” może zostać użyte jako identyfikator wirusa dla dowolnego programu, który nie jest naszym własnym programem antywirusowym.(Istnieją sposoby na „naprawienie” tego rozumowania, ale wymagają one dokładniejszego określenia naszych definicji).

@Nat `P` to skrypt

@Matthew Hah, opps, przegapiłem tę część!Wydaje się, że jest to sprzeczność, chociaż wydaje się być raczej problemem odnoszącym się do samego siebie, jak „_To stwierdzenie jest fałszywe._”, a nie klasyfikacją wirusów.

Program antywirusowy może zidentyfikować wszystko, co zawiera „DoVirusThings” jako wirus, ponieważ nie ma on zastosowania w programach innych niż wirusy i można go nazwać w inny sposób.

Wydaje mi się, że zakładasz, że „kod będący wirusem” jest w pełni skorelowany z „kodem, który wykonuje wirusy po wykonaniu”.To nie jest szalone założenie, ale mimo wszystko jest to założenie (i myślę, że przy tym założeniu twój dowód działa).

Hm, nie możesz łatwo wprowadzić `P` do funkcji, jeśli` P` ma być całym programem.Zamiast tego należy mieć „funkcję” „IsVirus” jako plik wykonywalny, który sprawdza obecność wirusów i podaje do niego bieżący plik wykonywalny jako nazwę pliku.Teraz programowi znacznie łatwiej jest „zasilić program antywirusowy” i stworzyć sprzeczność. jednak wtedy program `P` * będzie * robił wirusy, gdy jakiś plik wykonywalny` IsVirus` zwróci na nim fałsz, więc oznaczenie go jako wirusa jest w rzeczywistości poprawne.

stevegt

2019-01-24 05:21:03 UTC

view on stackexchange narkive permalink

Pierwotne pytanie brzmiało „Czy udowodniono matematycznie, że program antywirusowy nie może wykryć wszystkich wirusów?”

Można powiedzieć, że nigdy nie możemy udowodnić że napisaliśmy kod, który wykrywa wszystkie wirusy.

Komputer ogólnego przeznaczenia podłączony do Internetu z możliwością pobierania i wykonywania kodu jest prawdopodobnie odpowiednikiem uniwersalnej maszyny Turing. Ten ekwiwalent obejmuje nieskończony rozmiar taśmy Turinga: jeśli przepustowość interfejsu sieciowego maszyny jest mniejsza niż łączna szybkość wzrostu danych dostępnych w Internecie, maszyna nigdy nie osiągnie „końca taśmy”. (Omówiłem to trochę na zakończenie tego artykułu dawno temu. Chociaż można to udowodnić w sensie praktycznym, wymyślenie matematycznego dowodu prawdopodobnie wymagałoby dodania pewnych ograniczeń.)

Jeśli powyższe jest prawdą i jeśli „zatrzymać” oznacza „wygenerować raport zawierający wszystkie wirusy w systemie, nie więcej ani mniej”, to nie możemy z góry udowodnić, że program zatrzyma się z poprawnym odpowiedź; musimy to uruchomić, żeby się dowiedzieć.

Jeśli oba powyższe akapity są prawdziwe, nigdy nie możemy zweryfikować poprawności raportu wynikowego, ponieważ nigdy nie jesteśmy w stanie skompilować pełnej listy wszystkich możliwych wirusów, z którymi można by ją porównać: wszystkie te wirusy są dostępne gdzieś na taśmie ma nieskończony rozmiar i nigdy nie możemy przeczytać całości.

Jeśli wszystkie trzy akapity są prawdziwe, nigdy nie możemy udowodnić, że napisaliśmy w 100% poprawny wykrywacz wirusów.

Adithya Sama

2019-01-24 16:13:56 UTC

view on stackexchange narkive permalink

Cóż, definicja wirusa jest dość niejasna. Tak, jest to złośliwa jednostka, ale złośliwość jest równie niejasna. W zależności od systemu i jego zasad możliwości złośliwej jednostki zmienią się. Definiowanie ciągle zmieniającego się bytu to coś, co pojawiło się w różnych dziedzinach, teorii liczb, maszynach stanu itp. I zostało udowodnione na różne sposoby, że nie jest to możliwe, przynajmniej na podstawie tego, co wiemy.

Jednym ze sposobów byłby, zamiast definiować, co jest złośliwe, możemy zdefiniować, co jest dozwolone, bardzo rygorystyczny i niezależny system, który zezwala na wykonywanie tylko określonych sekwencji operacji. W ten sposób MOŻE być chronione.

Ten problem IMO jest tak samo trudny, jak zdefiniowanie losowego.

Bill K

2019-01-25 05:52:11 UTC

view on stackexchange narkive permalink

Wirus to tylko kod - to miło, jeśli mówisz „Czy mój program do kosiarki ze sztuczną inteligencją odróżnia chwasty od roślin” - jeśli tak, to czy ciągnie stokrotki?

Jeśli pobierzesz plik program, który wysyła e-maile do wszystkich na Twojej liście kontaktów, czy to wirus, czy jesteś spamerem? Zależy od tego, dlaczego pobrałeś program, a nie od konkretnej liczby bajtów w programie.

Więc nie musisz nawet przechodzić do matematycznego dowodu - możesz po prostu uzasadnić, że nie można tego zrobić.

Z drugiej strony można powiedzieć, że łatwo jest zidentyfikować wirusy, jeśli zdefiniujesz wirusa na podstawie zachowania. Programy są aktualizowane w ramach procesu aktualizacji, jeśli cokolwiek próbuje zmienić kod na Twoim komputerze poza tym procesem, możesz zdefiniować to jako wirusa. Dzięki tym definicjom można łatwo wykryć zmiany, które mają miejsce poza określonymi procedurami instalacji. Może to wymagać sprzętu, który może oddzielić kod od danych i zablokować przestrzeń kodu, gdy nie trzymasz przycisku, ale jest to możliwe (jeśli jest irytujące).

Zakłada się również, że kod, który celowo zainstalowałeś podczas procesu aktualizacji sam w sobie nie jest wirusem, ale ponieważ w tym przykładzie definiujemy wirusa według zachowania, to z definicji myślę, że tak nie jest.

guest271314

2019-01-28 02:13:56 UTC

view on stackexchange narkive permalink

Czy zostało matematycznie udowodnione, że program antywirusowy nie może wykryć wszystkich wirusów?

Do jakiej analizy odwoływał się Bruce Schneier, pisząc:

Wirusy nie mają "lekarstwo." Udowodniono matematycznie, że zawsze można napisać wirusa, którego żaden istniejący program antywirusowy nie może zatrzymać. ”[0]

[0] Secrets & Lies. Bruce Schneier. Strona 154

Ta odpowiedź nie odnosi się bezpośrednio do analizy, do której odwoływał się Bruce Schneier. Osoba zainteresowana tym, co oznaczało główne źródło, kiedy składała oświadczenie, powinna dołożyć starań, aby skontaktować się z głównym źródłem zadawać konkretne pytania , aby uniknąć spekulacji, domysłów lub zamieszania.

Twierdzenie o niezupełności Kurta Gödla opublikowane w 1931 roku w Über formal unentscheidbare Sätze der "Principia Mathematica" und verwandter Systeme (zwane po angielsku "O formalnie nierozstrzygalnych propozycjach" Principia Mathematica "i powiązanych systemów" ), kiedy dokładnie się rozważy, jest bardzo pouczające przy analizie dowolny system formalny, od wirusów komputerowych po politykę

1. Jeśli system (logiczny lub aksjomatyczny) jest spójny, nie może być kompletny.
2. Spójności aksjomatów nie można udowodnić w ich własnym systemie.

Te twierdzenia zakończyły półwiecze prób, poczynając od prac Frege'a, a kończąc na Principia Mathematica i Hilbert formalizmu, aby znaleźć zbiór aksjomatów wystarczający dla całej matematyki.

Z perspektywy czasu podstawowa idea leżąca u podstaw twierdzenia o niezupełności jest raczej prosta. Gödel zasadniczo skonstruował formułę, która twierdzi, że nie można jej udowodnić w danym systemie formalnym. Gdyby można było to udowodnić, byłoby to fałszywe. Tak więc zawsze będzie co najmniej jeden prawdziwe, ale nie dające się udowodnić stwierdzenie. Oznacza to, że dla każdego obliczalnie wyliczalnego zbioru aksjomatów dla arytmetyki (to jest zbioru, który w zasadzie może być wydrukowany przez wyidealizowany komputer z nieograniczonymi zasobami) istnieje wzór, który jest prawdziwy dla arytmetyki, ale którego nie można udowodnić w ten system. Aby było to precyzyjne, Gödel musiał jednak opracować metodę kodowania (jako liczb naturalnych) twierdzeń, dowodów i koncepcji możliwości udowodnienia; zrobił to używając procesu znanego jako numeracja Gödla.

Mr. E

2019-01-24 01:17:27 UTC

view on stackexchange narkive permalink

Nie jest to dowód matematyczny, ale AFAIK istnieją dwa sposoby wykrywania złośliwego oprogramowania:

Podpisy

W miarę tworzenia nowego złośliwego oprogramowania - w tym zaciemnianie lub modyfikowanie istniejących - sygnatura nowego złośliwego oprogramowania nie będzie w bazie antywirusowej, dlatego nie zostanie wykryta

Heurystyka

Ta metoda wykorzystuje automatyczną analizę dynamiczną i / lub statyczną, aby zrozumieć zachowanie oprogramowania i na podstawie tego, co robi, program antywirusowy decyduje, czy jest złośliwy, czy nie.

I tu jest trudna część, nie wszystko, co dziś jest uważane za nieszkodliwe, może nastąpić w przyszłości.

Na przykład 20 lat temu oprogramowanie korzystające z bibliotek szyfrujących mogło nie był postrzegany jako coś złośliwego, teraz wiemy, że może to być oprogramowanie ransomware szyfrujące Twoje dane. Jednocześnie możesz (i powinieneś) korzystać z menedżera haseł, który również używa bibliotek szyfrowania do bezpiecznego przechowywania danych. Jak więc możemy zdecydować, czy jest to złośliwe oprogramowanie, czy nie tylko na podstawie faktu, że szyfruje dane? Podobnie, połączenie TCP może służyć do wycieku informacji lub przeglądania stron internetowych.

Jedyna różnica polega na semantyce, która jest trudna do automatycznej analizy, ponieważ technologie stale się rozwijają, a złośliwe oprogramowanie dostosowuje się do tej ewolucji. W końcu złośliwe oprogramowanie nie różni się od innych programów poza złymi intencjami właściciela

Odpowiadasz na pytanie jak programista (którym jestem).To jest bezużyteczne.Ich pytanie nie dotyczy rzeczywistości, ale raczej teorii.To tak, jak wtedy, gdy próbuję przekonać ludzi, że żadna „sztuczna inteligencja” (sztuczna inteligencja) nie może być zła ani mieć duszy.Wskazują na jakieś badania lub artykuł na poziomie Elona Muska / Alexa Jonesa, a ja wskazuję na słowo „sztuczne”.Nadal nie będą słuchać.Bycie ekspertem nie pomaga w kłótni z większością ludzi.

„Bycie ekspertem nie pomaga w kłótni z większością ludzi”.Chociaż to prawda, pytają na stronie internetowej, której jedynym celem jest zapytanie „ekspertów” w tej dziedzinie.Po co pytać kogoś, kto nie chce przyjąć jego odpowiedzi?

Każdy jest ekspertem.

R.. GitHub STOP HELPING ICE

2019-01-23 22:24:54 UTC

view on stackexchange narkive permalink

Nie, nie zostało to udowodnione i nie można tego udowodnić, ponieważ to nieprawda. Program antywirusowy, który faktycznie działa, to po prostu odpowiedni model uprawnień / kontroli dostępu wymuszany przez środowisko wykonawcze. Twierdzenie Rice'a jest nieistotne, ponieważ nie musisz z wyprzedzeniem określać, czy program jest bezpieczny. Po prostu uruchamiasz go pod kontrolą dostępu i przerywasz (lub po prostu odmawiasz dostępu), jeśli próbuje zrobić coś niezgodnego z twoją polityką.

Matematycznie oznacza to, że masz obliczalny test, który daje pozytywny wynik wynik, jeśli program jest złośliwy , ale może nie zostać zatrzymany, jeśli program nie jest złośliwy. To dobrze, ponieważ test uruchamia program i możesz po prostu działać tak długo, jak długo nie jest złośliwy.

Oczywiście programy antywirusowe w prawdziwym świecie nie wykonują prostej, oczywiście właściwej rzeczy (która byłby zintegrowany z systemem operacyjnym, maszyną wirtualną środowiska wykonawczego lub podobnym komponentem, a nie oddzielnym produktem AV). Zamiast tego używają fałszywych sygnatur i heurystyk do klasyfikowania programów. Można udowodnić (zobacz inne odpowiedzi), że takie podejście nie może działać.

"Nie" co?Nie zostało to udowodnione?Ale przeczytaj inne odpowiedzi, które pokazują, że zostało to udowodnione?Bardzo zagmatwany początek Twojej odpowiedzi.Możesz wyjaśnić?

Nie jest bezpośrednią odpowiedzią na temat pytania.Opowiem o tym.

Czy mam usunąć wirusa, który używa rowhammera do nadpisania kontroli bezpieczeństwa jądra?

@Joshua: Środowisko wykonawcze może w pełni to wykryć lub zapobiec.Na przykład uruchamiając program pod tłumaczem.Zobacz „odpowiedni model kontroli dostępu”.W tym przypadku sprzęt jest wadliwy i umożliwienie jakiegokolwiek bezpośredniego dostępu niskiego poziomu do tej części systemu (wysyłanie żądań do magistrali pamięci) jest niewystarczającą kontrolą dostępu.

W przeciwieństwie do widma (jak dotąd), młot wioślarski można wykorzystać za pośrednictwem tłumacza.

Czy możesz * udowodnić * przypuszczalne istnienie tego * odpowiedniego środowiska uruchomieniowego *?

Załóżmy, że masz dwa programy: legalny program, który czyści stare pliki tymczasowe spełniające określone kryteria oraz złośliwy program, który usuwa ważne pliki spełniające określone kryteria.W jaki sposób mechanizmy kontroli dostępu w czasie wykonywania niezawodnie rozróżniają te przypadki?

@ulidtko: Tak.Formalne metody ludzie robią takie rzeczy przez cały czas, weryfikując projekty logiczne.Ale to zależy od sformalizowania reguł dotyczących tego, co jest dozwolone, a co nie.Wiele osób nie ma nawet na myśli modelu tego, co jest, a co nie jest złośliwe i oczekuje, że maszyna (lub inna osoba) będzie czytać w ich myślach i stosować normy społeczne od wewnątrz, aby podjąć decyzję.Oczywiście wydaje się to mało prawdopodobne.

@Ray: Kontrola dostępu umożliwia zapis / usuwanie jednego zestawu plików, a nie innego.Tak działają normalne uprawnienia systemu plików.

@Joshua: To zależy od charakteru tłumacza.Z całą pewnością nie można go wykorzystać na interpreterze, który permutuje adresy fizyczne i wirtualne za pomocą silnego szyfru kryptograficznego (bez również łamania szyfru) lub po prostu takiego, który ogranicza dostęp do pamięci w odpowiedni sposób.* Jeśli * Twój fizyczny komputer podlega takim błędom, * wtedy * Twoja kontrola dostępu musi obejmować środki uniemożliwiające dostęp do mechanizmów wywołujących te błędy.To nie jest fizyka jądrowa, ludzie.

Chociaż jest dobry, nie zapobiegnie wszystkim wirusom.@Ray umożliwił pominięcie problemu w tym konkretnym przykładzie, ale nie zawsze tak będzie.A co z tym, gdzie _ dokładnie to samo oprogramowanie_ może być postrzegane w jednym przypadku jako użyteczne, a w innym jako złośliwe?Weź pod uwagę oprogramowanie, które umożliwia zdalne sterowanie komputerem, napisane i używane początkowo na dobre.Potem inni go nadużywają.Gracz nazywa to niesamowite, gdy jego kumpel daje mu XP, gdy śpi, a ich sąsiad uważa to za szkodliwe, gdy ich wróg wysyła nieprzyjemny biały szum.Śmieci jednej osoby to skarb drugiej osoby.

@Aaron: ** Po raz n-ty **, czyli kwestia wyboru odpowiedniego modelu kontroli dostępu / zdefiniowania złośliwego.

Poza tonem, moja odpowiedź jest w zasadzie taka sama, jak odpowiedź [James_pic's answer] (https://security.stackexchange.com/a/202047/2836), która pojawiła się później i nie jest tak śmiesznie negatywnie oceniana przez osoby, które tego nie zrobiłyprzeczytaj komentarze.

Ta odpowiedź wyjaśnia, jak zapobiegać uruchamianiu _nieautoryzowanych programów_, a nie wirusów w szczególności.Pytanie dotyczy w szczególności złośliwego oprogramowania.

@forest: Malware to po prostu program, który robi coś, czego nie chcesz, aby robił.

@R .. napisał "wybierając odpowiednią kontrolę dostępu ..." Jeśli to takie proste, to powinieneś napisać o tym artykuł.Ponieważ w konkretnym przykładzie, który podałem, jeśli rzeczywiście możesz napisać taką kontrolę dostępu lub definicję, aby odróżnić „Akcja A jest w porządku” i „(dokładnie to samo) Akcja A jest złośliwa”, zostałbyś milionerem.Nie, jeszcze lepiej, ponieważ całkowicie zaprzeczyłbyś samej logice i odkryłbyś zupełnie nowy rodzaj logiki, który to umożliwiłby, możesz zostać miliarderem lub być w stanie przeciwstawić się fizyce dzięki nowej logice i stać się supermanem.

... chodzi mi o to, że dokładnie to samo, to samo, ta sama akcja może być zarówno złośliwa **, jak i ** nie złośliwa.Oczywiście nie w tym samym miejscu w tym samym czasie.Ale w innym miejscu lub w innym czasie.Może nawet na tym samym komputerze, z tymi samymi kontrolami dostępu, wykonując tę samą czynność (ten sam plik, ta sama modyfikacja itp.), Ale Susy uważa to za dobrą rzecz, a pół godziny później, gdy jej brat używa komputera, który uważato złośliwe.Albo Susy uważa, że jest złośliwy w czasie X, ale nie w Y („aplikacja play-me-a-tune” jest fajna w czasie wolnym, ale można ją łatwo wykorzystać jako złośliwe oprogramowanie)

@R .. Chcę powtórzyć, jesteś na dobrej drodze.Moje komentarze nie oznaczają inaczej.Lepsza kontrola dostępu znacznie poprawiłaby blokowanie złośliwego oprogramowania.Proponujesz ogromną poprawę w stosunku do nowoczesnego antywirusa.Kwestie, które są przeciwko niemu podnoszone, są po prostu takie, że w tym konkretnym pytaniu i odpowiedzi osoba zadająca pytanie bardzo szczegółowo zapytała o dowody matematyczne dotyczące tego, czy można wykryć _ każde możliwe_ złośliwe oprogramowanie.Musimy założyć, że oznacza to minimalną liczbę fałszywych alarmów, w przeciwnym razie odpowiedź brzmi „zablokuj wszystko”.Tak więc, gdy „p! = Q” i „p = q” są prawdziwe, nasze komentarze sugerują, że nie może.

Podstawowy pomysł tej odpowiedzi wydaje się poprawny, chociaż ramka jest wyłączona - w szczególności wygląda na to, że ta odpowiedź dotyczy nieco innego pytania, ale źle sformułowana, aby pasowała do tego pytania.Problem w tym, że chodzi o to, jak analizować program w celu ustalenia, czy jest to wirus na podstawie jego specyfikacji, np.plik binarny, którego ta odpowiedź nawet nie próbuje rozwiązać.Wydaje mi się jednak, że ta odpowiedź jest rodzajem wyzwania związanego z ramką, ponieważ powodem, dla którego nie próbuje odpowiedzieć na to pytanie, jest to, że proponuje lepsze rozwiązanie niż program antywirusowy: zarządzanie w czasie wykonywania.

marshal craft

2019-01-24 13:47:47 UTC

view on stackexchange narkive permalink

Sam zgodziłbym się z Najibem. Twierdzenia o modelach można zawsze stosować tylko do bardzo formalnego logicznego podzbioru logiki formalnej. Nie wiem, czy na podstawie jakiejś formalnej gramatyki logicznej można sformułować cokolwiek o niekompletności rzeczywistości. W pewnym momencie wydaje się, że jest to kwestia większej filozofii. To powiedziawszy, zakładając, że możesz konkretnie opisać, co to znaczy być wirusem lub złośliwym oprogramowaniem, to znaczy, że można to sformułować jako pytanie matematyczne, a następnie z pewnością można to pokazać.

Komputery mają ograniczone zasoby. Tak więc za pomocą brutalnej siły można rozważyć każdy stan i jeśli jest on złośliwy.

Może to się nie powiedzie, jeśli weźmie się pod uwagę kombinacje stanów w czasie? Nie mogę powiedzieć siebie.

kubanczyk

2019-01-23 17:10:37 UTC

view on stackexchange narkive permalink

Czy możemy mieć program antywirusowy wykrywający wszystkie wirusy?

Nie potrzeba matematyki. Czas na eksperyment. Zorganizujmy pulę wirusów, pulę systemów, które próbują się bronić, i mechanizmów, które nieustannie zmieniają / ulepszają obie strony.

Daj im planetę. Poczekaj miliardy lat.

Czy nadal mamy wirusy?

Dla mnie sama liczba przetestowanych już możliwości jest daleko poza zadowalającą.

O „dowodzeniu”

Tutaj chciałbym wyjaśnić, dlaczego drastycznie przeformułowałem Twoje pytanie.

Bezpośrednia odpowiedź na Twoje pytanie „Czy zostało udowodnione matematycznie, że <statement o prawdziwym świecie>” to: Nie, matematycy nigdy nie udowodnili twojego twierdzenia o prawdziwym świecie (ani żadnego innego podobnego stwierdzenia). Przez świat rzeczywisty mam na myśli ten, który widzisz, kiedy patrzysz przez okno.

Możesz udowodnić wszystko tylko w systemach aksjomatycznych („światach” rządzonych zbiorem aksjomaty - gdzie same aksjomaty są zdefiniowane jako niemożliwe do udowodnienia). Nie znam aksjomatów, które rządzą prawdziwymi wirusami komputerowymi, więc nie mogę niczego na ich temat udowodnić.

Postaram się przewidzieć rzeczywistość i często będę miał rację. Ale użyję do tego fałszywych teorii, a nie dowodów.

Twój argument idzie trochę za daleko w innym kierunku - istnieją oczywiste luki w tym, co ewolucja biologiczna może praktycznie osiągnąć (żadna krowa nie przeskoczyła księżyca), a brak „rozwiązań” pewnych „problemów” jest trudny do zaakceptowaniajako absolutny dowód, że czegoś nie da się zrobić, chyba że zademonstrujesz, dlaczego nie możemy zrobić nic lepszego.W szczególności mechanizmy „ewolucji” i „selekcji” wirusów i oprogramowania antywirusowego są zupełnie inne.Nawet słowo „wirus” stało się mylące, jeśli chodzi o obecne złośliwe oprogramowanie (które rzadko się kopiuje).

@JeroenMostert Właśnie zgłosiłem fakt.Chociaż sugerujesz, że majstrowanie w myślach w naszych głowach dałoby bardziej zadowalające rezultaty, w tym przypadku liczba powtórzeń i ogromne zbiorniki próbek są dla mnie wystarczające.To znaczy, zakładam, że jest znacznie bardziej prawdopodobne, że ludzki mózg coś tu przeoczy, niż cała biosfera sprawdzająca to przez tak wiele pokoleń.(Ale - tak! - w niektórych innych przypadkach nasze myślenie może być oczywiście lepsze. To dobrze dla nas!)

Samochody są niemożliwe.Dowód: miliardy lat ewolucji nie przyniosły kół.co było do okazaniaTo oczywiście się nie udaje, ponieważ podobieństwa między biologią a inżynierią sięgają tylko tak daleko - nie trzeba nawet zakładać inteligentnych wynalazców.Podobnie informatyka.Zauważyliśmy kilka uroczych podobieństw między replikacją programów i biologicznych wirusów dawno temu, ale to na tyle daleko, że rzeczywiste replikujące się programy stały się jedynie teoretycznymi ciekawostkami, podczas gdy złośliwe programy są martwe, ale działają.Czy biologiczna paralela jest nadal aktualna i wnikliwa?Nie zakładałbym.

@JeroenMostert Tak, myślę, że też o tym wspomniałem.

Nie chodzi o to, czy dowody są możliwe, czy nie.Masz krok na bok, odpowiadając na pytanie.Poczyniono odniesienie i ramy zostały wykonane w tym kontekście.To jest brak odpowiedzi.

@schroeder Ach, to jest ważna obawa - zredagowałem się, aby poprawić swoje pominięcie.

Oprócz braków wskazanych w poprzednich komentarzach, odpowiedź ta (prawdopodobnie przypadkowo) w sposób dorozumiany opiera się na błędnych założeniach dotyczących równoważności wirusów biologicznych i komputerowych.To, że oba nazywane są „wirusami”, nie oznacza, że mają identyczne odpowiednie właściwości.Nazwa jest metaforą, a nie dokładną definicją.

** Procesy ewolucyjne nie optymalizują się **;są [satysfakcjonujące] (https://en.wikipedia.org/wiki/Satisficing).Nie można twierdzić, że niepowodzenie systemu ewolucyjnego w opracowaniu optymalnej strategii przeciwko wrogiemu agentowi dowodzi jego niemożliwości.Jestem też prawie pewien, że OP nie dba o system aksjomatyczny użyty w dowodzie.Nikt nie potępiłby cię za używanie [aksjomatów Zermelo – Fraenkla] (https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory#Axioms), a wskazywanie na jego problemy jest czerwonym śledziem.

Marshall Whittaker

2019-01-24 00:04:43 UTC

view on stackexchange narkive permalink

Mniej więcej tak. Matematyka, która za tym stoi w kategoriach laika, sprowadza się do paradoksu bootstrapingu, rodzaju czasowego paradoksu, który kwestionuje, skąd pochodzi informacja. Odnosi się to do tego problemu, ponieważ jeśli masz program antywirusowy, który wykrywa wszystkie znane wirusy, ale następnego dnia ktoś utworzy nowy wirus, w starym skanowaniu wirusów nie będzie sygnatury wykrywającej nowy wirus silny>. Gdybyś mógł zabrać wszystkie wirusy komputerowe od końca czasów, przesłać je do przeszłości i stworzyć z nich wszystkie sygnatury wirusów, skąd się wzięły te informacje ? Przyszłość czy przeszłość? Ponieważ ogólny konsensus jest taki, że podróże w czasie są niemożliwe z wielu powodów matematycznych / fizycznych, nie możesz objąć wszystkich wirusów , a jedynie wszystkie znane wirusy.

Opiera się to na nieokreślonym założeniu, że „programy antywirusowe nie mogą wykryć wirusów, które nie istniały lub nie były znane, kiedy program antywirusowy był tworzony / ostatnio aktualizowany”.To jest klucz do pytania, więc założenie, że to prawda, oznacza, że twoja odpowiedź nie ma rzeczywistego znaczenia.Ponadto w przypadku ** niektórych ** wirusów to założenie jest wyraźnie fałszywe, ponieważ heurystyka działa na niektórych wirusach.Cała rozmowa o podróżach w czasie to po prostu bzdury.