Les versions 0.1 des codes Flex et Ruby sont disponibles dans la rubrique "Téléchargements".

Le projet peut être également vu sur savannah. Un accès au code CVS est possible.

Le code Flex est le plus fonctionnel. Codé en C avec Flex comme analyseur syntaxique, il est très rapide.

Les librairies nécessaires sont (sur un ubuntu Breezy Badger)

• libmpfr-dev (2.1.1-11)
• libgmp3-dev (4.1.4-10ubuntu1)
• libdb4.3++-dev (4.3.28-1ubuntu3)
• libdb4.3++c2 (4.3.28-1ubuntu3)
• libdb4.3-dev (4.3.28-1ubuntu3)

Le code est disponible sur l’hébergeur de projets savannah, dans la rubrique Téléchargement pour les tarballs ou bien dans la rubrique CVS.

— > ICI <—

La commande ./tokenize -h affichera l’aide et les options d’exécution du programme.

Il est ensuite aisé d’écrire des scripts qui vont récupérer les adresses visitées dans les logs d’un proxy (à l’aide d’expressions régulières) avant de les traiter puis de les ajouter à une liste noire si besoin est.

Je suis preneur de ce genre de scripts afin des les mettre accessibles dans une section sur ce site.

L’archive délivrée ici contient 2655 pages ’pornographiques’ et 2357 pages ’non pronographiques’.

Elle peut être utilisée pour créer la base d’apprentissage quelque soit le programme utilisé (Code Ruby, Qt ou flex).

Je la fournit telle quelle, elle mérite encore de l’attention afin d’être améliorée ; peut y-a-il trop de pages, peut être ne sont-elles pas assez représentatives du type de contenu...

Elle est disponible ICI.

Le code en Ruby a été le langage de prototypage du projet. Il est cependant fonctionnel.

Les paquets nécessaires sont :

• ruby (1.8)
• libdb-ruby (libdb4.2-ruby1.8)
• libgmp-ruby : http://raa.ruby-lang.org/project/libgmp-ruby/
• ruby1.8-dev : Si lors de la commande ./extconf.rb pour l’installation de libgmp un message d’erreur indique que mkmf n’est pas présent (distribution Debian).

Le code est disponible sur l’hébergeur de projets savannah, dans la rubrique Téléchargement pour les tarballs ou bien dans la rubrique CVS.

— > ICI <—

Pour son exécution ./filter.rb -h indiquera les options possibles.

Il est ensuite possible d’écrire des scripts qui vont récupérer les adresses des pages visitées depuis le log d’un proxy (ou autre) pour les mettre en entrée de ce programme. Suivant le résultat retourné ces adresses peuvent alors être ajoutées ou non en liste noire.

Je suis preneur de ce genre de scripts afin des les mettre accessibles sur ce site.

Voici les différentes sources qui m’ont permis de rédiger ce document et de développer les différents programmes :

LE BOUCLIER. Les 12-17 ans connaissent deux fois plus internet que les adultes [en ligne]. Disponible sur http://www.bouclier.org/article/2834.html (consulté le 30.06.2005).

ROBINSON Gary. A Statistical Approach to the Spam Problem [en ligne].2003. Disponible sur : http://www.linuxjournal.com/article/6467 (consulté le 30.06.2005).

LOUIS Greg. Greg’s Bogofilter Page [en ligne]. Disponible sur : http://www.bgl.nu/ glouis/bogofilter/ (consulté de 30.06.2005).

LOUIS Greg. Really Bayesian Bogofilter [en ligne]. 2003. Disponible sur : http://www.bgl.nu/bogofilter/bayes.html (consulté le 30.06.2005).

Méthodes bayésiennes en analyse statistique [en ligne]. Disponible sur : http://cdfinfo.in2p3.fr/Experiences/Cosmologie/Techniques/bayes1.html (consulté le 30.06.2005).

SHAYNE C. Gad. Meta Analysis. In : Statistics and Experimental Design for Toxicologists. 3rd ed. CRC Press, 1998, p.171.

FRIEDL E.F. Jeffrey. Maîtrise des expressions régulières. O’REILLY&Associates, 2002.

LONGMAN Wesley Addison. Ruby Class and Library Reference [en ligne]. Disponible sur : http://www.rubycentral.com/ref/ (consulté le 30.06.2005).

THOMAS Dave. Programming Ruby, The Pragmatic Programmers’ Guide. The Pragmatic Programmers, 2005. 49

RAA - Ruby Application Archive [en ligne]. Disponible sur : http://raa.ruby-lang.org/ (consulté le 30.06.2005).

The Lex & Yacc Page [en ligne]. Disponible sur : http://dinosaur.compilertools.net/ (consulté le 30.06.2005).

BERNARD Etienne. Mini manuel d’utilisation de Lex et Yacc [en ligne]. Disponible sur : http://pltplp.net/lex-yacc/index.html.fr (consulté le 30.06.2005).

Flex - GNU Project - Free Software Foundation (FSF) [en ligne]. Disponible sur : http://www.gnu.org/software/flex/ (consulté le 30.06.2005).

Au fur et a mesure de la détection, sachant quelle expression régulière a rencontré le token désiré on est en mesure de savoir quel est son type.
On peut alors le stocker.
Pour ce faire il faut d’abord découper les tokens déjà récupérés (les balises html et les mots) suivant des séparateurs afin d’obtenir des tokens plus petits et plus précis, quant à ce qu’ils représentent, puis d’indiquer avant le token quel est son type (balise, domaine, mot ou bi-mot).

Nos besoins sont de pouvoir stocker un des tokens et le nombre d’occurrences correspondantes. Il s’agit en fait de stocker une paire clé/données dans laquelle la clé est le token (qui est unique) et les données sont les nombres d’occurrences (dans les catégories autorisée et interdite) ce token.

Il n’y a pas de requête complexe à effectuer sur cette base. On veut juste pouvoir stocker la paire et y accéder rapidement lors de l’attribution de score.

Sleepycat Software a développé Berkeley DB qui correspond exactement à nos attentes.
En effet, Berkeley DB permet de stocker des données sous la forme (clé) / (données) dans laquelle la clé est unique.
Pour ce qui est de la structure nous sommes libre de choisir entre un hash, un B-Arbre, ou une file. De plus elle permet de gérer la taille de la mémoire tampon afin d’optimiser la vitesse d’accès aux données.

Cet outil semble donc être celui qui nous est nécessaire par ces méthodes de stockage ainsi que ces méthodes d’accès aux données optimisées. Nous arrêterons donc notre choix sur cette base de données.

Cependant nous devons stocker un couple de valeurs par clé, et afin d’optimiser l’espace stockage il faut coder ce couple.

Plutôt que de stocker deux entiers on va coder les valeurs sur quatre octets (deux fois deux octets, soit deux octets par entier) pour stocker d’une par le nombre d’occurrences autorisées et d’autre part le nombre d’occurrences interdites.

Le nombre maximal que l’on peut coder sur 1 octet est 2⁸ - 1 = 255 et on peut coder 2⁸ = 256 valeurs (de 0 à 255).
De même sur 2 octets on peut coder 256² = 65536 (de 0 à 65535).
Un nombre en base 10 peut donc s’écrire sous la forme : X₁₀ = a₂₅₆ + b₂₅₆.

Ce qui nous donne :

• a = E(x/256)
• b = Xmod(256)

Comme un token n’est compté qu’une fois par page lors de l’apprentissage (et est codé sur deux octets), il faudrait avoir 65536 pages en apprentissage, dans l’une ou l’autre catégorie, pour que la zone mémoire soit dépassée. On a donc une bonne marge de sécurité quand à cette valeur limite.

Les expressions régulières sont des outils extrêmement puissants et précis qui permettent de reconnaître des formes (ou pattern) dans du texte.
Elles vont donc être très utiles ici afin de supprimer le code dont on ne veut pas (commentaires, java scripts, feuilles de styles etc.), et afin de détecter les tokens que l’on souhaite récupérer et stocker.

Pour rappel il faut récupérer les balises HTML, les noms de domaines (qui peuvent être dans des balises ou pas), et enfin les mots et les bi-mots.

Chacune des étapes à réaliser peut se résumer en une seule expression régulière. Je vais les détailler ici en langage Ruby (qui a été le langage de prototypage) mais elles sont très similaires à celles utilisées avec la librairies QT de KDE ou encore avec Flex.

Les tokens détectés sont les suivants.

Les noms de domaines

Comme on peut trouver les noms de domaines aussi bien dans les balises HTML que dans le texte, on commence par les détecter au cas où le code serait ultérieurement altéré.

Elle permet de détecter :

• toute chaîne commençant par http:// ou bien https:// - par le https ? :\/\/,
• suivi d’un mot (suite de lettres) ou d’un nombre (suite de chiffres) - détectés par \w - ou d’un tiret ou d’un point, et ce au moins une fois.

Comme on ne cherche pas à détecter de slash (’/’) la détection s’arrêtera au premier slash rencontré ou bien au premier espace ou tout autre caractère non recherché.
On obtiendra donc bien les noms de domaines.

Les balises HTML (tags)

Afin de récupérer seulement les tags nécessaires il nous faut tout d’abord supprimer tous ceux qui sont inutiles.

Elle permet de détecter :

• les commentaires qui commencent par <!--, finissent par --> et peuvent contenir tout ce que l’on veut et même des retours à la ligne,
• ainsi que les scripts (de la même manière).

Une fois ces expressions rencontrées dans le texte on les supprime.
On peut maintenant récupérer toutes les autres balises, qui nous intéressent.

On récupère :

• tout texte commençant par un chevron ouvrant et se terminant par un chevron fermant,
• qui peut contenir n’importe quoi entre doubles guillemets ou simples guillemets ou n’importe quoi sans ces symboles et sans chevron fermant.

On supprime ces tokens du code HTML en même temps qu’on les détecte.

Les mots

On dispose maintenant de la page HTML dont tout le code a été supprimé. On peut donc récupérer le texte après s’être séparé des caractères encombrant :

Tout les caractères non significatifs sont supprimés (&nbsp;, &lt;, &#[\\d]+;).

On détecte également tous les caractères d’accentuation (&eacute;, &egrave; etc.) ou caractères spéciaux (&ccedil;) pour les remplacer par les caractères normaux correspondants (e, c etc.).

On peut finalement récupérer les mots, ensembles de lettres, de chiffres et des caractères de ponctuation ($ !?+%@=-), les autres caractères non détectés faisant offices de séparateurs.

Exemple

L’application des expressions régulières et des séparateurs nous donnera les tokens suivants :
Noms de domaines :
domain :ac-rouen.fr
Balises HTML :
tag :a
tag :a_href
tag :a_http
tag :a_www
tag :a_ac
tag :a_rouen
tag :a_fr
Mots
word :Rectorat
word :de
word :Rouen
Bi-mots
biword :Rectorat_de
biword :de_Rouen

A ce stade, nous disposons déjà d’une base de données contenant les tokens, avec leur nombre d’occurrences, provenant des pages traitées lors de l’apprentissage.

Une page au contenu inconnu peut alors être tokenisée à son tour. Chaque token trouvé dans cette page est alors recherché dans la base d’apprentissage afin de calculer la probabilité qu’elle soit classée comme interdite sachant qu’elle contient ce token.

La méthode statistique mise en oeuvre dans le projet est tirée des calculs utilisés dans les logiciels de détection de Spam. Elle est basée sur des calculs bayésiens et se divise en quatre étapes :

• le calcul de probabilités individuelles,
• l’altération de ces probabilités,
• La combinaison de toutes les probabilités individuelles,
• Le calcul d’un indicateur global sur la page.

Probabilités individuelles

Pour chaque constituant de la page tokenisée (balises, domaines, mots et bi-mots) il est tout d’abord nécessaire de calculer leurs probabilités individuelles. Un token est cette fois comptabilisé autant de fois qu’il apparaît dans une page. Pour ce faire nous nous basons sur les valeurs (occurrences) stockées en base d’apprentissage. Pour chaque token qui apparaît dans la page nous calculons :

• b(w) (b comme “bad” et w comme “word”) qui représente le nombre de pages interdites contenant le mot “w” (noté Card(B|wεB)) divisé par le nombre total de pages interdites (Card(B)).
  
  
  Proportion d’occurrences interdites d’un mot
  
  
• g(w) (g comme “good”) qui représente le nombre de pages autorisées contenant le mot “w” (noté Card(G|wεG)) divisé par le nombre total de pages autorisées (Card(G)).
  
  Proportion d’occurrences autorisées d’un mot
  
  
• p(w) qui peut être interprété comme la probabilité qu’une page choisie aléatoirement et contenant le mot “w” soit une page interdite.
  
  Probabilité individuelle

Ces probabilités obtenues pour chaque token présent dans la page peuvent ensuite être combinées pour attribuer un score et ainsi catégoriser la page en question.

On peut cependant noter un problème dans ce calcul. En effet lors de l’apprentissage tous les mots pouvant exister (de n’importe quelle langue) n’ont pas forcément été rencontrés plusieurs où même une seule fois. Il en va de même pour les balises HTML et leur contenu ; il est impossible d’en avoir une liste exhaustive suite à l’apprentissage étant donnée l’étendue des possibilités offertes (ne serait-ce que sur le choix d’une couleur).
Ainsi pour un token n’ayant été rencontré qu’une seule fois lors de l’apprentissage ce calcul donne trop d’importance à la probabilité individuelle correspondante.

Exemple 1 :
Pour simplifier les choses nous dirons que nous avons autant de pages interdites et autorisées en apprentissage ce qui donne le calcul de probabilité individuelle :

Admettons maintenant que nous voulons calculer la probabilité relative à un token, trouvé dans une page que l’on désire catégoriser, et que celui-ci n’est apparu qu’une seule fois lors de l’apprentissage dans une page interdite.
On obtiendra donc : p(w)=1/(1+0)=1

Exemple 2 :
Prenons un token ayant 10 occurrences interdites et 1 autorisée.
On aura : p(w)=(10)/(10+1)=0.91

Or notre expérience nous montre que la première probabilité ne peut être de 1, nous ne pouvons pas être certains que ce mot désigne une page interdite, nous manquons seulement de données à son sujet. De même pour le deuxième exemple.
Il nous faut donc trouver un moyen d’altérer ces probabilités afin de diminuer la force qui leur est attribuée.

Altération

La méthode suivante permet de prendre en compte les mots rares c’est à dire ceux n’apparaissant pas souvent, voir jamais, lors de l’apprentissage.
Cette méthode nous est fournie par les statistiques bayésiennes qui permettent de traiter ce genre de cas avec efficacité. Le principe est d’attribuer un degré de confiance à un évènement donné.
Ceci nous permet d’ajouter notre expérience aux données et valeurs collectées lors de l’apprentissage.
Nous calculons ce degré de confiance basé sur le calcul précédent de p(w) comme suit :

• s est la force donnée à notre expérience
• x est la probabilité assumée qu’un mot que l’on ne connaît pas appartienne à la catégorie interdite
• n est le nombre de pages contenant le token w

Pour commencer ces valeurs sont initialisées à 1 pour s et 0.5 pour x. Il faudra ensuite les modifier en testant plusieurs pages pour tenter d’optimiser les résultats.
Maintenant nous utiliserons f(w) plutôt que p(w) car ce dernier ne donne pas des résultats réalistes prenant en compte notre expérience.

Reprenons les exemples précédents avec s=4 et x=0.45 :
Exemple 1 :f(w)=((4×0.45)+(1×1))/(4+1)=0.56 et non plus 1
Exemple 2 :f(w)=((4×0.45)+(11×0.95))/(4+11)=0.79 et non plus 0.91

La force donnée à un mot rare est donc maintenant beaucoup plus faible. L’exemple 1 qui avait avant une probabilité plus forte que l’exemple 2 est maintenant plus faible comme cela doit l’être réellement aux vues de notre expérience.

Explications

Afin d’expliquer ce calcul prenons pour exemple le jeu de pile ou face. Il y a n lancers effectués, chaque lancer est un essai et nous comptabilisons le nombre de face obtenu. Il s’agit d’un test suivant une loi binomiale (il y a deux valeurs, pile et face), de plus chaque lancer est indépendant.
On peut ainsi calculer la probabilité que le n+unième lancer donne une face par le calcul suivant :

• q est le nombre de succès (nombre de fois où l’on a obtenu ’face’)
• n est le nombre de lancers
• u et v sont les paramètres de la loi binomiale (ici et dans la supposition que la pièce n’est pas biaisée u=v=0.5)

On peut maintenant rapporter ce calcul au cas nous concernant. Lors de la recherche de la probabilité individuelle d’un token, nous réalisons un essai indépendant des autres (le fait qu’une page contienne le mot ’porn’ n’est pas corrélé au fait que la prochaine le contienne également), pouvant avoir deux issues (autorisée ou interdite). Nous sommes donc dans le même cas que le lancer de pièce et la probabilité qu’une page contenant un token donné appartienne à la catégorie interdite suit une loi binomiale.

Si on pose, dans l’équation précédente :

• u = s × x
• v = s × (1 - x)
• q = n × p(w)

On retrouve alors :

En essayant avec s = 1 et x = 0.5 (les paramètres de départ) on obtient les paramètres de la loi binomiale : u = v = 0.5.
Donc nos paramètres de départ ont été choisis en faisant l’hypothèse d’équiprobabilité des évènements (un token inconnu a autant de chance d’appartenir à une page autorisée qu’à une page interdite).

Avec le calcul de f(w) plutôt que p(w) nos résultats devraient être plus précis.

Il est maintenant temps de combiner les différentes probabilités afin d’obtenir un score global de la page.

Combinaisons de probabilités

Nous sommes donc maintenant capables de calculer les probabilités individuelles de chaque token rencontré dans une page, basées sur notre expérience et sur les données stockées en base.
Chaque page peut être alors représentée par un ensemble de probabilités. Il nous faut combiner cet ensemble de probabilités afin de produire un indicateur correct du contenu de la page.

Reprenons l’exemple du lancer de pièce.
Si nous partons avec l’hypothèse de départ que cette pièce n’est pas biaisée, et lançons 10 fois la pièce et obtenons 10 fois face, la probabilité globale sera de (1/ 2)¹⁰ = 1/1024 . Ce serait un événement très peu probable en prenant en compte l’hypothèse de départ.
Mais en rejetant cette hypothèse de départ et à la place prendre celle qui dit que la pièce est biaisée, alors ce résultat deviendrait normal.

Une méthode a été écrite par R.A. Fisher (1932), qui, appliquée à notre modèle permet de tirer le même genre de conclusion, en l’occurrence de rejeter ou valider une hypothèse de départ.

Notre hypothèse de départ est : "les probabilités individuelles sont précises, et les pages pour lesquelles ont attribue les scores sont une collection aléatoire de tokens, indépendants les uns par rapport aux autres, tels que ces probabilités suivent une loi uniforme."

La méthode de combinaison de Fisher permet de combiner les probabilités de n études indépendantes. Les n probabilités p₁ ,p₂ ,..., p_n représentent un échantillon indépendant de la loi binomiale.
Il est noter que dans le cas de non indépendance des probabilités individuelles, la méthode de Ficher conduit à des obtenir de grandes valeurs qui nous permettent de rejeter notre hypothèse de départ.

Les étapes du calcul sont :

• tout d’abord calculer -2lnΠp-(i)
• puis considérer que le résultat obtenu suit une distribution du Chi² avec 2n degrés de liberté,
• enfin utiliser une table du Chi² afin d’obtenir la probabilité combinée,
• Cette probabilité est censée résumer toutes les probabilités individuelles.

Dans notre cas les n études indépendantes sont les n tokens récupérés dans la page pour laquelle on désire attribuer un score.

La formule globale est :

Où C-^-1 est la fonction de du Chi² inverse.
Le cas où les probabilités individuelles sont dépendantes nous donne des résultats élevés nous intéresse particulièrement. En effet on cherche à rejeter notre hypothèse de départ car on sait très bien qu’une page Web n’est pas une collection aléatoire de tokens. L’ensemble des tokens d’une page Web a un sens et ils sont donc dépendants les uns des autres.

Un score proche de 0 nous permettra donc de rejeter notre hypothèse de départ et à la place prendre celle qui dit que la page à laquelle on attribue un score appartient à la catégorie autorisée.
Un score proche de 1, au contraire, nous fera choisir l’hypothèse de départ selon laquelle la page appartient à la catégorie interdite.

Indicateur global pour la page

Le résultat précédent nous pose cependant problème dans le sens où la combinaison présente une faiblesse. En effet dans ce calcul du produit des logarithmes les valeurs faibles (proches de 0) apporteront plus de poids dans le résultat final que les valeurs proches de 1 (dans un produit de valeurs comprises entre 0 et 1 les valeurs proches de 0 font tendre celui-ci vers 0 plus rapidement que les valeurs proches de 1 ne le font tendre vers 1).

Sachant que la méthode de combinaison de Fisher est basé sur un produit de valeurs on en déduit que les pages appartenant à la catégorie autorisée sont avantagées par ce calcul.

Cependant, il a des moyens de gérer ce problème qui n’apporte pas de tendance à mal classifier les pages autorisées en interdites.

La méthode la plus efficace est la suivante :

• Inverser les probabilités individuelles en les soustrayant à la valeur 1, soit calculer, pour chaque tokenf, 1-f(w-). Comme les f(w) représentent la probabilité qu’une page prise aléatoirement parmi l’ensemble des pages contenant le mot w soit une page interdite, 1-f(w) est la probabilité qu’une telle page soit autorisée.
• Effectuer la même combinaison de Fisher que celle vue précédemment mais cette fois en combinant les 1-f(w). Cette combinaison est appelée S :
  
  S = C-^-1 (—2lnΠ-(1 — f(w)),2n)
• Enfin calculer :
  
  Indicateur global de la page
  
  I est un indicateur qui sera proche de 1 quand la majorité des probabilités sera en faveur de la conclusion que la page est interdite et sera proche de 0 dans le cas contraire (page autorisée).

  A ce point et afin d’améliorer les résultats pour qu’ils soient réellement proches de 0 ou de 1, le meilleur moyen est de supprimer, lors de la combinaison des probabilités individuelles, celles à faible déviation, c’est-à-dire qui font tendre le résultat vers 0.5. Ces probabilités sont 28 principalement dues à des tokens non présents en base d’apprentissage et ils sont extrêmement nombreux ce qui peut fausser les calculs. La déviation peut être bien évidemment réglée et 0.4 (les probabilités comprises entre 0.4 et 0.6 seront supprimées du calcul final) semble être un bon point de départ.

Il regroupe les deux étapes vues précédemment (tokenisation et stockage des tokens). Le but est ici de disposer d’un ensemble de pages représentatives des catégories autorisée et interdite. Il faut de même un nombre conséquent de ces pages afin que l’apprentissage soit bon, et que les données stockées soient en assez grand nombre pour couvrir une plage correcte du vocabulaire et des différents tokens qui peuvent être rencontrés sur le Web et ce, afin de pouvoir ensuite attribuer des scores à des pages inconnues.

Ces pages représentatives sont alors tokenisées et les tokens les constituants stockés en base de données suivant leur type (balise HTML, nom de domaine mot ou bi-mot) avec leur nombre d’occurrences. Un token apparaissant plusieurs fois sur une page n’est comptabilisé qu’une seule fois, mais peut apparaître sur plusieurs.

Lors de la récupération des tokens, à chaque page, il nous faut les stocker :

• de façon temporaire en phase d’apprentissage comme en phase d’attribution de score, afin de pouvoir les traiter de la manière dont chaque phase l’exige,
• de façon permanente pour le stockage des tokens et de leur nombre d’occurrences (une base d’apprentissage).

Le meilleur moyen est de stocker ces tokens en base de données. Il n’est pas nécessaire d’utiliser une base de données de type traditionnel (SQL), car les requêtes effectuées seront limitées à écrire ou bien lire les nombres d’occurrences d’un token dans les catégories autorisée ou interdite.

Il nous faut donc une base de stockage de type hash ou arbre qui nous permette de stocker une paire (clé) / (valeur) correspondant à (token) / (nombre d’occurrences).