Pomiędzy bitami

Trochę z rozpędu po ostatnim spojrzeniu na beznadziejną captchę na Blox, trochę zażenowany brakiem działania administratorów Blox w tak wydawałoby się prostej sprawie, trochę chcąc odkurzyć stare skrypty i znajomość Perla, trochę ze względu na zainteresowaniem tematem spamu, a w końcu trochę dla zabawy, postanowiłem zrobić przymiarkę do automatycznego wykrywania spamu na Blox. Chodzi o określanie, czy dany blog służy wyłącznie spamowaniu, oczywiście automatycznie, a co za tym idzie nie ze stuprocentową pewnością.

Administratorzy zapowiedzieli, że captcha zostanie poprawiona w kwietniu (trzymam za słowo i liczę na to, zapewne nie tylko ja), więc spamblogów nie powinno od tej pory przybywać. Zatem postanowiłem skupić się nie na liście nowozałożonych blogów, tylko na liście nowych wpisów, czyli aktywnych spamblogach. Co prawda pierwotny plan zakładał przeiterowanie się po wszystkich blogach i określenie prawdopodobieństwa, czy jest to spamblog, ale nie znalazłem niestety listy wszystkich blogów na Blox. Owszem, można próbować robić rzeźbę pod tytułem "przeiterujmy się po tagach", ale nadal nie daje to gwarancji uzyskania listy wszystkich blogów - wystarczy, że ktoś nie taguje i system nie dotrze do jego bloga, więc stanęło na tym, że obserwuję listę nowych wpisów i stamtąd biorę dane. Przy okazji oceniam nie tyle cały blog, co poszczególne wpisy, co może być przydatne.

Podejście pierwsze - pobierz i oceń. Na samym początku stwierdziłem, że będę pobierał wpis do oceny i oceniał na podstawie arbitralnych kryteriów. Pomysł szybko upadł - zmiany w algorytmie oceniania powodowały niekompatybilność z poprzednimi danymi, a zmiany były konieczne - wychodziły coraz to nowe kryteria i ich wagi. Wersjonowanie algorytmu przy ocenie nie pomagało, bo dane były tracone. OK, nie jest to wszystko aż tak proste, jak się wydawało na początku.

Podejście drugie - pobierz i zapisz jak najwięcej cech wyróżniających dla danego wpisu/bloga, a potem pomyśli się nad algorytmem. No niestety, zapisywanie dużej ilości danych może być ciekawe, szczególnie, że potem można sięgnąć do wiedzy ze studiów i określić poziomy istotności poszczególnych parametrów (albo popytać kumpla o gotowca, może jeszcze ma...). Wytrenuje się AI na próbce kontrolnej, a potem AI sama zrobi resztę. Brzmi fajnie, ale trochę overkill, poza tym, mało odporne na dołożenie kolejnych parametrów, gdyby przyszło mi do głowy ich wyciąganie.

Podejście trzecie, aktualne,kompromisowe - pobierz i zapisz istotne (wybrane arbitralnie przeze mnie) cechy wyróżniające dany wpis. Osobny skrypt ma algorytm procentowy, każda cecha może przyjmować wartości 0-100% prawdopodobieństwa bycia spamem. Następnie w zależności od ilości cech wylicz prawdopodobieństwo dla całego wpisu przy pomocy średniej ważonej. Rezultaty są dość interesujące.

Tutaj lista blogów, które sklasyfikowałem jako spamerskie z prawdopodobieństwem 80% i więcej. Format prawdopodobieństwo bycia spamem (%), spacja, link do bloga. Nie widzę (szybko patrząc) żadnego false positive, a wy? Aktualnie jest takich blogów 375 na 2404 wszystkich sprawdzonych blogów. Jasne, nie jest to cud techniki, ale przy dodaniu pewnych prostych whitelist myślę, że można spokojnie blokować automatem wszystkie blogi z prawdopodobieństwem od 70% w górę.

Szczegółów badanych cech oraz algorytmu nie chcę na razie opisywać, bo po co spamerzy mają się bronić? Jak będzie utrudnione zakładanie nowych blogów, to pomyślę o tym. Na razie cały czas zbierają się dane... Gdyby byli chętni do przeglądania wyniku w celu wychwytywania false positive'ów (wpisujcie miasta, które przeglądają ;-)), to mogę pomyśleć o wystawianiu listy spamów automatem co jakiś czas.

Całość napisana oczywiście w Perlu, główny moduł zbierający z użyciem WWW::Mechanize (genialna sprawa do crawlerów).

UPDATE: Drobny update statystyk z dnia 27.04.2012 - 13481 unikatowe blogi (wcześniej chyba były unikatowe wpisy, ale mniejsza), w tym 1094 do natychmiastowego wycięcia (80% i więcej). Dla porządku 70% i więcej to 2438 sztuki. Listy nie zamieszczam, bo zainteresowanie było znikome. A captcha nadal nie została poprawiona, choć koniec kwietnia...

Co jakiś czas łapię się na tym, że robię porządki, zmiany, podsumowania i postanowienia. Zwykle grupowo i w okolicach urlopów. Jako, że właśnie skończyłem urlop, to pora na małe podsumowanie.

Na początek rzeczy z publicznej listy TODO. Przede wszystkim, w końcu uruchomiłem produkcyjnie Dockstara. Póki co - działa i podoba mi się. Prawie pewne jest też, że pojawi się wkrótce test sprzętowego simlocka - muszę (i to szybko!) przenieść numer spam z Plusa, zapewne do Play, bo długie terminy po doładowaniach, a numer tylko na przychodzące. Zobaczymy jak to działa, zobaczymy co dalej z telefonami...

Znowu lenistwo wzięło górę i nie poszukałem kasety Bez Krótkich Spodni. Numer jeden do zrobienia przy najbliższej okazji, razem z (dopisanym w tej chwili) eksportem archiwum listy SzLUUG. Router w domu... kiedyś zrobię, najpierw kable trzeba zabezpieczyć jakoś, bo małą ciągnie i gotowa zepsuć połamać. Certyfikat IPv6 ugrzązł. Chciałem robić tylko w oparciu o publiczne, darmowe zasoby i poległem na revDNS - wygląda, że nikt z dynDNSów nie umożliwia ustawienia reva (albo za słabo poszukałem, po prostu).

Z innych sieciowych rzeczy - dziś przypadkiem sprawdziłem i okazało się, że Google podniósł blogowi pagerank (do 4). Co ciekawe, staremu, nieutrzymywanemu blogowi nie spada (nadal 3). Przypominają się ludzie ze starych projektów. Tydzień na zastanowienie i trzeba sobie jasno odpowiedzieć, czy jest sens się bawić czy kolejne rzeczy do zaorania. Tym bardziej, że są nowe plany (nie nadają się na publiczne TODO) i czas będzie potrzebny.

Z nie wpisanych na listę - zacząłem klepać kod do gry. Tak, zainspirowałem się historią RPG Idee Fixe, które powstawało latami i stwierdziłem, że skoro nic podobnego do tkwiącego w mojej głowie pomysłu nie istnieje (albo przynajmniej o istnieniu nie wiem), to będę pomału rzeźbić, bo pośpiechu nie ma. Na razie bawię się pojedynczymi funkcjami, nie wiem jeszcze, czy miałoby być to webowe, czy standalone. O ile cokolwiek powstanie, co wcale pewne nie jest... Na razie jest pomysł (miejscami mglisty), do tego napiszę parę funkcji i postaram się złożyć to w spójną całość. Potem pozostało dobranie parametrów (czytaj: prawdopodobieństw) i jakby to wyszło, to tylko pozostanie opakować w formę strawną dla przeciętnego użytkownika (czytaj: nie CLI).

Czy naprawdę piątek przypada trzynastego dnia miesiąca częściej, niż inne dni tygodnia, jak wynika z tego wpisu? Postanowiłem to sprawdzić, metodą najdoskonalszą, czyli brute force. Co prawda tylko dla lat 1970-2037 czyli w Unix Epoch (pełne lata).

Kod był praktycznie gotowy z czasów obliczeń, czy pracownicy zyskają, czy stracą na wolnym 6. stycznia. Ostatecznie wygląda on tak:

a wynik działania wygląda tak:

DOW - ilosc
1 - 116
2 - 118
3 - 115
4 - 117
5 - 117
6 - 116
7 - 117
Suma: 816

1 - Monday, ... , 7 - Sunday

Piątek oznaczony jest cyfrą 5, jak widać występuje on jako trzynasty dzień miesiąca 117 razy, podobnie jak czwartek i niedziela , więcej w badanym okresie jest wtorków trzynastego (118), a najmniej śród (113).

Pozostaje pytanie, dla jakich dokładnie lat prowadzona była analiza w oryginalnym wpisie. Na oko wygląda na jakieś 335 lat, pytanie które dokładnie. W każdym razie w badanym okresie nic nie wskazuje na większą częstotliwość występowania piątku w trzynasty dzień miesiąca.

• 1 stycznia
• 1 maja
• 3 maja
• 15 sierpnia
• 1 listopada
• 11 listopada
• 25 grudnia
• 26 grudnia

(pomijam 4 święta ruchome, które w Polsce nigdy nie wypadają w sobotę), a do tego dochodzi od tego roku 6 stycznia.

Nie wdając się w matematykę (jakoś nie mam głowy do matematyki kalendarzowej, a nic sensownego mi nie wyszło przez chwilę namysłu), korzystam z metody najdoskonalszej, czyli pełnego przeglądu (AKA brute force) wg algorytmu: jeśli któreś z dotychczasowych świąt wypadnie w sobotę, to pracownicy tracą dzień, jeśli 6 stycznia nie wypadnie w sobotę ani w niedzielę, to pracownicy zyskują dzień.  I sumowanie strat i zysków...

Całość to nieładny bash (funkcja date) napędzana perlem, pisany na szybko.

Wynik? Miłe złego początki - przez najbliższe 10 lat stracimy, jako pracownicy, średnio rocznie 0,1 dnia wolnego, a w pierwszych 3 latach nawet będzie niewielki zysk, ale dla 25 lat - o ile przepisy się nie zmienią - stracimy łącznie 8 dni wolnych, czyli 0,32 dnia wolnego rocznie. Szczerze mówiąc, nie jest tak źle jak myślałem...

Ale zmiana jest ewidentnie niekorzystna dla pracowników. Gdyby miała miejsce w 1990 roku, to do tego roku tracilibyśmy średnio ponad pół dnia wolnego rocznie.

I skrypt do obliczeń:

Temat (nie)unikatowych numerów kont pojawił się w tej dyskusji nt. tokenów, a szerzej opisany jest w tym wpisie, ile cyfr potrzeba, by numer rachunku bankowego był unikatowy. Przyznam, że nie miałem zielonego pojęcia nt. algorytmu weryfikacji numeru IBAN, ale na chłopski rozum kolizje zdarzą się wszędzie. Stwierdziłem, że najlepsza metoda nauki to napisać skrypt do sprawdzania. Oczywiście w Perlu. Przy okazji wyszło mi, że Perl średnio sobie radzi z dużymi liczbami, a Python dobrze, ale dzięki temu znalazłem pięknego gotowca w postaci modułu do sprawdzania poprawności numeru IBAN.

Pierwsze, co rzuca się w oczy, to fakt, że tak naprawdę numer IBAN jest zamieniany na liczbę, a czy jest poprawny określane jest tylko na podstawie jednego testu - jeśli reszta z dzielenia tej dużej cyfry przez 97 wynosi 1, to numer jest poprawny.

Chwila zabawy programem i okazuje się, że dla 3 brakujących cyfr w dowolnym miejscu rachunku można wygenerować ok. 10 kolizji. Pewnie ma to coś wspólnego z faktem, że 97 jest liczbą pierwszą, a samo 97 mieści się w każdym tysiącu właśnie 10-11 razy, ale tutaj już by się matematyk przydał i zasady podzielności przez 97 (hasło do Google cechy podzielności przez 97 nic sensownego nie znalazło niestety).

Inna szansa, że nasze PL na początku numeru (które wraz z następującymi po nim dwiema cyframi jest przesuwane na koniec i zamieniane na liczby patrz algorytm weryfikacji numeru IBAN) jest na tyle pechowe, że powoduje taką przykrą przypadłość. Ale to łatwo sprawdzić - dzięki użyciu ogólnej biblioteki skrypcik do bruteforce'owania numerów IBAN powinien działać dla wszystkich krajów.

Póki co konkluzja jest taka, że aby numer był unikatowy, to trzeba podać wszystkie cyfry. Przy dobrym wietrze może się zdarzyć, że 1 można opuścić.

PS. Nie cierpię słowa unikalny. Dla mnie oznacza ono możliwy do uniknięcia. Zamiast niego możnaby używać słowa unikatowy. Niestety SJP traktuje je jako synonimy.

Przy okazji chęci uporządkowania (może rozwoju) mojego μbloga identi.ca pojawił się odwieczny problem: jak znaleźć znajomych w identi.ca (w ogólności: w serwisie mikroblogowym)? Po chwili namysłu stwierdziłem, że najprostszym sposobem szukania znajomych jest przeglądanie znajomych moich znajomych. Skoro ja znam A, a A zna B, to stosunkowo spora szansa, że znam B lub że chcę go dodać do obserwowanych. Podobnie tematycznie - ludzie zwykle obserwują ludzi o podobnych zainteresowaniach.

Najprostszy wariant, ręczny, to otworzenie przeglądarki, otworzenie profili wszystkich znajomych w kartach, następnie dla każdego profilu otworzenie wszystkich obserwowanych. Teoretycznie dobre, w praktyce szybko zrobiłoby się kilkadziesiąt/kilkaset kart, na dodatek z powtarzającymi się profilami. Nie tędy droga.

Ponieważ identi.ca ma API, to postanowiłem sprawdzić, czy nie uda się lekko sobie pomóc skryptem. Okazało się, że w Perlu jest moduł do obsługi API identi.ca o nazwie Net::Identica. Tak naprawdę API identi.ca i Twittera jest identyczne (do Twittera jest Net::Twitter), ale stwierdziłem, że dodam w systemie dedykowany moduł. Co prawda nie ma go w repozytorium debianowym, ale stosunkowo łatwo go zbudować (po spełnieniu zależności) z użyciem dh-perl-make.UPDATE: Ostatecznie korzystam jednak z Net::Twitter.

Ponieważ sądzę, że pytanie jak znaleźć znajomych na Twitterze (czy też na identi.ca) zadaje sobie sporo ludzi, postanowiłem opublikować skrypt, może komuś się przyda. W skrypcie należy podać ID usera, od którego ma zacząć poszukiwania, login i hasło. Nie polecam zmieniać poziomu głębokości poszukiwań (domyślnie jest to znajomi znajomych).

Algorytm jest prosty: dopóki nie osiągnie zadanego poziomu głębokości (domyślnie 2 czyli znajomi znajomych), to pobierze wszystkie ID użytkowników będących znajomymi obecnego użytkownika i doda je do sprawdzenia. Z kolei sprawdzanego użytkownika oznaczy jako sprawdzanego (i nie będzie go sprawdzał po raz kolejny). Zaczynamy od wskazanego ID użytkownika (przypuszczalnie własnego).

W zasadzie tyle. Na koniec pobierze i wyświetli dla wszystkich zebranych ID, których nie mamy już w znajomych podstawowe dane - nazwę, link do profilu, opis itp. - raczej wystarczy, by określić, czy chcemy dodać daną osobę do obserwowanych, czy nie. Bonusowo ID użytkownika, który jest zakończeniem najkrótszej (jednej z najkrótszych) ścieżek do nowopoznanej osoby.

W trakcie pojawił się drobny problem - znajomych znajomych było ponad 3k. Przypuszczałem, że jest jakiś błąd w skrypcie, ale po bliższym przyjrzeniu się wyszło na jaw, że winny jest rms (tak, Richard M. Stallman), który obserwuje właśnie tyle osób. Na takie okazje została dodana blacklista - wystarczy podać tam ID użytkownika, którego znajomych nie chcemy sprawdzać (w ogóle).

Na koniec skrypt wyświetli nam podstawowe dane, jak dla mnie wystarczające, by zorienotwać się, czy chcemy dodać kogoś do obserwowanych. Zasadniczo nic nie stoi na przeszkodzie, by dodać ich (po ID) skryptem, ale ja wolę wejść na profil i zobaczyć najpierw, co piszą (tak, oznacza to, że prawdopodobnie niebawem będę intensywniej korzystał z identi.ca, kosztem Blipa).

Skrypt poniżej. Przy okazji być może jest to sposób na nieirytujące zamieszczanie kodu na Blox...

UPDATE: Nie bardzo chciały działać URLe, przeszedłem na Net::Twitter i zamieszcam poprawioną wersję.

UPDATE2: Jest w komentarzu, ale nie wszyscy docierają: Jak znaleźć ID użytkownika na Twitterze? ID użytkownika na Twitterze (na Identi.ca też) jest zawarta w feedzie RSS danego użytkownika.

BadRAM był fajny, ale jest nieutrzymywany. Ostatnią działająca u mnie wersja była do kernela 2.6.25.x, późniejsze, choć istniały (np. dla 2.6.29), to nie udało się ich - wbrew wcześniejszej radości - zmusić do poprawnego działania - nadal pojawiały się błędy np. na liczeniu sum kontrolnych.

Sama idea zabawy w porozumiewanie się kalkulatorem została przybliżona tutaj, i zapowiedziałem automacik. Oto i on.

#!/usr/bin/perl

$file="/usr/share/dict/polish";
$regexp='^[osildebzjkhbgr]+$';
$regexp_strict='^([osiebzlkbg]+|[osiebzlhbg]+|[osiebzlrbg]+|[osjebzlkbg]+ \
|[osjebzlhbg]+|[osjebzlrbg]+|[dsiebzlkbg]+|[dsiebzlhbg]+|[dsiebzlrbg]+ \
|[dsjebzlkbg]+|[dsjebzlhbg]+|[dsjebzlrbg]+)$';
$strict=1;

if ($strict){
  $regexp=$regexp_strict;
}

open(F,$file);
while (<F>){
  if (/$regexp/o){
    chomp;
    print "$_ ";

    y/odilkhrszebjg/0011444523879/;

    @tmp=split //;
    $num=0;
    while (@tmp){
      $lit = pop @tmp;
        if ((! $num) && ($lit =="0")){
          print "$lit.";
        }
      else{
        print $lit;
      }
      $num++;
    }
    print $/;
  }
}
close (F);

Zmienna $file to oczywiście pełna ścieżka do pliku z wyrazami (jeden per linię), które sprawdzamy. W tym przypadku systemowy słownik języka polskiego. Zmienna $strict określa, czy chcemy, aby dana cyfra określała w obrębie wyrazu tylko jedną literę.

Jako wynik otrzymujemy gotowe do wpisania na kalkulator ciągi cyfr. Skrypcik jest b. prosty, pisany na szybko, więc możliwe są błędy. Za ich wskazanie będę wdzięczny. Have fun!

UPDATE: Poprawiony błąd zgłoszony przez inS.

UPDATE2: Poprawiony błąd w linii s/[g]/9/; -> s/[g]/9/g;

UPDATE3: Wdałem się we flame o językach programowania, co zmobilizowało mnie do lekkiego sprzątnięcia (tr zamiast kilku s) i optymalizacji kodu (/o) - jest jakieś 15% szybciej, choć nie o to w tym chodzi.