Aggirare un CAPTCHA per divertimento e divulgazione – Parte 5

Questo è il quinto articolo della serie sui CAPTCHA – meglio tornare al primo se non l’hai già letto.

Riassunto delle puntate precedenti

Ecco la ricetta per “leggere” il CAPTCHA di Vodafone!

  • rimuovere il rumore dal fondo dell’immagine, per sottrazione con un’immagine di solo rumore ottenuta comparando molti CAPTCHA;
  • applicare un filtro a soglia per rendere netti i contorni dei caratteri;
  • opzionalmente, correggere le aree bianche o nere troppo piccole e (semi)isolate dal resto;
  • segmentare l’immagine nei vari caratteri, ad esempio con un algoritmo flood fill;
  • ridimensionare ogni lettera individuata a 15×15 pixel;
  • dare in pasto ogni carattere a una rete neurale a percettrone propriamente allenata.

Ciò detto, quale è l’accuratezza del sistema?

Risultati

Ho testato un’implementazione dell’algoritmo di cui sopra e i risultati sono stati i seguenti:

  1. il CAPTCHA viene decodificato correttamente al primo tentativo in più del 90% dei casi su un campione di circa 100 immagini;
  2. come spiegato nella parte 4 questo dato si riferisce a prove fatte su un campione di immagini diverse da quelle usate per l’allenamento della rete neurale (cross-validation), quindi la percentuale del 90% è rappresentativa dell’accuratezza reale;
  3. ovviamente, se la decodifica non funziona al primo colpo si può ritentare. Visto che basta un solo tentativo a buon fine per rompere la protezione fornita dal CAPTCHA, la probabilità di successo nella pratica è ancora più alta: con con 3 tentativi si sbaglia su una sola lettura su mille, e con 6 tentativi una su un milione!

Note statistiche: nella ragionevolissima ipotesi che gli esiti delle letture di CAPTCHA siano indipendenti, segue che i risultati del punto 1 sono sufficienti per affermare che la percentuale di successo è sopra al 90% con significatività del 99%. Quanto descritto al punto 3 discende dalla stessa ipotesi, in quanto la probabilità P di successo complessiva è data da

P = 1-[(1-p)(1-p)(1-p)…] n volte


dove p è la probabilità di successo del singolo tentativo ed n il numero di tentativi.

Tecniche implementative

Nota Bene: i prossimi paragrafi sono dedicati ai programmatori ed alle persone con esperienza in ambito informatico – è normale che non risulti di facile comprensione agli altri lettori.

Come si possono tradurre in pratica le idee esposte fino a questo punto? Io ho usato questi strumenti:

Scala

Il linguaggio Scala è stato scelto per due ragioni:

  1. è molto, molto compatibile con Java, permettendo in particolare di utilizzare librerie e classi Java esistenti. Naturalmente questo fa molto comodo per usare Encog, che è scritto proprio in Java!
  2. rispetto a Java ha alcune caratteristiche interessanti, che se ben usate portano produrre a codice, a mio parere, molto più compatto e leggibile.

Ad esempio, è possibile definire classi i cui oggetti si usano come i vettori. Sembra inutile? Si pensi a come semplifica la vita poter scrivere codice come questo in una libreria che fa trattamento di immagini:

if (image(2, 3) == BLACK)){
    image(2, 3) = WHITE
}

Sfido qualunque programmatore a non capire il significato! E’ interessante anche notare che, per raggiungere questo risultato, non c’è bisogno di sintassi astruse, basta infatti definire due metodi particolari, apply ed update, come nell’esempio che segue:

class Image(...) {
    def apply(x:Int, y:Int):Int = {
        // ritorna in un intero il colore alla posizione (x,y)
    }
    def update(x:Int, y:Int, color:Int):Unit = {
        // cambia in color il colore del pixel alla posizione (x,y)
    }
}

Ancora una volta, a mio parere, estremamente leggibile. Ho usato codice di questo tipo per costruire un wrapper attorno a java.awt.Image, la classe Java per la gestione delle immagini, ottenendo una classe allo stesso tempo potente e semplice, in poche righe di codice.

Un’altra chicca simile è la possibilità di definire metodi con nomi strani, ad esempio +, oppure |, ridefinendo in pratica gli operatori del linguaggio per classi specifiche. Ho usato questa particolarità per implementare i filtri delle immagini con una sintassi simile a quella delle shell Unix.

Credo che sia immediato capire il senso di questo codice:

image = read(new FileInputStream(file))
filteredImage = image | new DesaturateFilter() | new RemovePatternFilter(new FileInputStream("data/pattern.png")) | new ThresholdFilter(170) | ...

Per poter scrivere la riga di cui sopra basta implementare il metodo | di Image e definire una “classe astratta” che rappresenti un filtro:

class Image(...) {
  def |(filter:ImageFilter):Image = {
    filter.filter(this)
  }
}
trait ImageFilter {
  def filter(image:Image):Image
}

E’ da notare come in Scala è possibile usare semplici spazi al posto dell’operatore “.” tipico di Java, e si possano anche omettere le parentesi ove non ambiguo, e questo permette di scrivere

filteredImage = image | filter

al posto di

filteredImage = image.|(filter)

A mio parere, un vero colpo di genio! Scegliendo nomi appropriati per i metodi, infatti, questa caratteristica da sola porta a scrivere codice molto più simile al linguaggio naturale, quindi facile da comprendere, rispetto alle controparti Java. Altri esempi illuminanti:

count = collection size
heightInPixels = image height
calculator compute inputs

In questi esempi si sarà notato che sono omessi anche i terminatori di riga (“;” in Java). Questo è l’ennesimo piccolo beneficio di Scala: i terminatori si possono omettere ovunque non sia ambiguo. Perchè consumare tasti inutilmente?

Un’altro aspetto che mi piace molto di Scala è che nonostante sia un linguaggio staticamente tipato (come Java e a differenza di Groovy, Ruby o Python) non costringe ad usare sintassi prolissa per specificare i tipi degli oggetti ovunque. Mi spiego: supponendo di avere un metodo che accetta un oggetto Car e poi lo usa, in Java occorre scrivere qualcosa del tipo:

Brick demolish(Car car){
  Car myCar = car;
  return myCar.demolish();
}

In questo esempio, i tipi in grassetto non sono strettamente necessari: è evidente che myCar debba essere di tipo Car (poichè car è di tipo Car), analogamente dal momento che il metodo ritorna sempre e solo il risultato di Car.demolish() è ovvio che il risultato sia un’istanza di Brick. In Scala, dal momento che tutto questo è superfluo, può essere omesso:

def demolish(car:Car){
  val myCar = car;
  return myCar demolish
}

Il compilatore controlla tutti i tipi e completa le definizioni ovunque possibile, il che risparmia un bel po’ di digitazioni inutili (e facili da sbagliare). Ovviamente in caso di ambiguità ci sarà una segnalazione di errore, solo in quel caso sarà necessario specificare i tipi come in Java. L’aspetto interessante è che si arriva a scritture concise simili a quelle dei linguaggi tipati dinamicamente senza rinunciare agli utili controlli di coerenza del compilatore.

Encog

L’uso di Encog di per sè non è particolarmente bizzarro, nel senso che segue esattamente l’interfaccia Java documentata sul sito ufficiale. Ad esempio, questo è il codice per caricare una rete neurale allenata con l’Encog Workbench:

network = new BasicNetworkPersistor().load(new ReadXML(new FileInputStream("model.eg"))).asInstanceOf[BasicNetwork]

L’unica cosa degna di nota è l’ultima parte, asInstanceOf[BasicNetwork], che è l’equivalente di un cast in Java richiesto dal fatto che BasicNetworkPersistor.load() ritorna un EncogPersistedObject che è una sopraclasse di BasicNetwork. L’uso della rete vera e propria è addirittura banale:

inputs = new BasicNeuralData(rawInputs toArray)
outputs = network compute inputs

dove rawInputs non è che una List[Double].

Ecco il codice!

Viste le tecniche principali ed alcune curiosità sulla stesura del codice non resta, per chi ha ancora voglia di studiare, che prendere in mano il codice sorgente del programma!

Scarica il Progetto Eclipse per la decodifica dei CAPTCHA (zip, 1MB)

Il progetto contiene:

  • la cartella training che contiene un sufficiente numero di CAPTCHA scaricati e decodificati manualmente per l’allenamento;
  • il package net.moioli.moiosms.imagefilters contenente le implementazioni in Scala dei filtri grafici descritti nelle puntate precedenti;
  • il package net.moioli.moiosms.training contenente:
    • il programma TrainingImagePreparer che prende i CAPTCHA nella cartella training, applica i filtri grafici e li scompone in singole lettere divise per allenamento e validazione;
    • il programma TrainingCsvGenerator che, prendendo le lettere generate dal programma precedente, crea file CSV che possono essere importati in Encog Workbench;
  • data/letters.eg, un esempio di rete Encog già allenata in questo modo e soprattutto
  • OCRTester, un programma che legge effettivamente i CAPTCHA come descritto in questi articoli!

Il modo più semplice per provare tutto questo è:

  1. installare l’ultima versione di Eclipse per Java;
  2. installare il plugin Scala-IDE, che contiene il compilatore Scala;
  3. decomprimere lo zip;
  4. importare il progetto (menù File, Import…, General, Existing Project into Workspace);
  5. lanciare uno dei programmi con la voce Run as… Scala Application dal menù che compare cliccando con il tasto destro sul file corrispondente.

Dovreste ritrovarvi con una schermata simile alla seguente:

Conclusioni

Con questo articolo chiudo la serie sui CAPTCHA iniziata qualche mese fa. So che non è molto rispetto alla fine del progetto MoioSMS ma spero possa essere un adeguato punto di ripartenza per chi volesse ricominciarlo o semplicemente ampliare le proprie conoscenze. Scrivete pure nei commenti opinioni e domande!

10 Comments

  • Molto istruttivo. 😉

  • Ben scritto, chiaro e semplice come al solito. Thumbs up!

  • Domanda stupida: ma nei captcha con i caratteri che non sono (facilmente) separabili da flood fill? (ergo con caratteri che si toccano)

  • La domanda è tutt’altro che stupida! Se leggi il capitolo relativo sul Russel-Norvig trovi scritto che la separazione tra i caratteri è esattamente la parte più difficile di qualunque progetto di riconoscimento automatico dei caratteri (è la cosa che al momento è più faticosa da insegnare ad una macchina).

    Un’idea che era venuta a me è stata di usare le reti neurali per stimare delle linee (nei casi semplici verticali) di separazione tra i caratteri, anche se chiaramente si commette qualche errore. Un’alternativa forse più furba sarebbe tentare di riconoscere le lettere a coppie, o a terne. Altra possibilità è di scomporre la scritta in tratti (curve parametriche più o meno delimitate) e poi di raggruppare i tratti in lettere, sapendo che non tutte le combinazioni sono valide. O ancora: usare degli algoritmi di clustering per raggruppare i pixel in lettere, anche se probabilmente sarebbe difficile scrivere una buona funzione di stima della distanza tra i pixel. Al momento non mi vengono altri colpi di genio, direi comunque che dipende tutto dal particolare CAPTCHA che si tenta di analizzare; se hai altre idee o trovi articoli a riguardo sarei felice di approfondire!

  • L’argomento è molto interessante per voi programmatori, ma lo è ancora di più per noi utenti disabili visivi. Infatti, essendoci nelle procedure di registrazione questi captcha che, per noi sono la negazione assoluta per potersi registrare ad un sito (il meno visto che si fa una sola volta) oppure quando siamo costretti ad usare un form ripetitivamente, siamo in forte difficoltà e non sempre possiamo usufruire di un occhio in prestito. Siccome c’è già un servizio per Mozilla Firefox (www.webvisum.com) non è possibile creare lo stesso plug-in per Internet Explorer? Voi che siete programmatori, pensateci! Farete sicuramente una opera buona per tantissimi disabili visivi, ma anche per tantissime persone anziane la cui vista non sempre è delle migliori.
    In ogni caso vi ringrazio e vi auguro buon lavoro.

  • Desidero ringraziarti per questa guida molto ben fatta ed istruttiva. Grazie a questa guida sono riuscito a creare un software OCR scritto in php per decodificare il captcha vodafone, e da integrare in gojack, un software scritto sempre da me, in php per l’invio di sms. In verità ho seguito la guida solo nelle parti iniziali..per la separazione enormalizzazione delle immagini, mentre poi per il riconoscimento non ho usato reti neurali, ma ho fatto di testa mia, converrtendo l’immagine resa in bianco e nero in una matrice (array multidimensionale) e dopodicchè si tratta solo di confrontare gruppi di dati e fare un rapporto percentuale di ogni confronto. Grazie ancora. E auguri per il tuo futuro.

  • ciao. Bellissima guida!
    Perdona una stupida domanda: è possibile eseguire l’ocrtester anche per immagini non presenti nella cartella training? Ho provato a creare un semplice captcha con estensione .jpg e a metterlo in quella directory, ma non c’è verso che venga letto.
    Grazie e complimenti per il lavoro!

  • Si potrebbe, anche se chiaramente è necessario intervenire sul codice per far leggere il formato diverso. Ho usato PNG ovunque per evitare perdite di informazioni dovute alla compressione.

    Grazie dei complimenti!

  • Ciao Silvio. Non so se hai notato, ma il captcha storico della vodafone è stato modificato, insieme a tutto il servizio vodafone sms. Quel captcha, di cui tu avevi raccolto 180 esemplari, è durato forse 10 anni. Come tutte le cose era destinato al cambiamento. Il software che avevo scritto, e per il quale ti ho ringraziato, ha continuato a leggere il captcha vodafone per poco più di un anno (sopra puoi trovare il mio commento). E’ stato sostituito dai recaptcha. Pensi si possano leggere con un ocr? Ovviamente sono molto più complessi. Da oggi si può dire, che queste tue guide, per chi le leggerà, analizzano un captcha che purtroppo potremmo definire un “pezzo da museo”. Ciao!

  • Grazie per la segnalazione, in effetti non uso il sito da un pezzo e come dici, c’era da stupirsi che il meccanismo fosse ancora in uso. Spero comunque che il materiale possa essere utile come “esempio semplificato” per chi si appresta ad imparare qualcosa in materia!

    Tra le altre cose ho in programma qualche grosso cambiamento al sito, che vorrei indirizzare maggiormente agli attuali aspetti professionali. Si partirà con un articolo su PostgreSQL. Stay tuned!

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>