Pour éviter les intrusions frauduleuses dans un réseau, un système de surveillance enregistre les tentatives de connexions.
Toute tentative est modélisé par un tuple (adresse_ip, statut, timestamp_en_ms), où :

• adresse_IP est l'adresse IPv4 de la machine voulant se connecter au réseau sous forme d'une chaîne de caractères,

• statut est une chaîne de caractères valant soit "échec", soit "succès, chaîne modélisant la réussite à la connexion ou non,

• timestamp_en_ms est le nombre entier donnant l'instant, à la milliseconde près, de la tentative de connexion au serveur.

L'ensemble des tentatives est stocké dans une liste logs

Dans cet exercice, on considère qu'une attaque par force brute est tentée depuis une adresse IP donnée si 5 échecs consécutifs sont rencontrés en moins de 10 secondes.
Cette adresse IP est alors blacklistée.

À chaque adresse IP est associée une file stockant au maximum 5 tentatives de connexions.
Cette file est implémentée sous forme d'un tuple (tableau, tete, queue), tableau étant une liste de taille fixe valant 6, tete est l'indice de l'élément de tableau correspondant à la tête de la file et queue correspond à l'indice de la case de la liste tableau où doit être stocké le prochain élément à enfiler ; queue pointe donc toujours vers un élément vide ou n'ayant plus de sens concret.
Chaque élément stocké dans la liste tableau sera un entier timestamp_en_ms.

Partie A : Gestions des primitives de la file

1. Pourquoi implémenter avec un tableau de taille fixe est préférable à une implémentation avec un tableau liste taille variable où queue prendrait automatiquement la valeur len(liste) ?

2. Quitte à vous aidez de la partie implémentation d'une file par une tableau circulaire, compléter les primitives suivantes :

   def file_vide(file):
       """Renvoie True si la file implémentée sous la forme (tableau, tete, queue) est vide."""
       return ...
   
   def taille(file):
       """Renvoie le nombre d'éléments dans la file circulaire 
       implémentée sous la forme (tableau, tete, queue) où liste est de taille 6.
       """
       queue = ...
       tete = ...
       if queue >= tete:
           return ...
       else:
           return ...
   
   def est_pleine(file):
       """Retourne True si la file implémentée sous la forme (tableau, tete, queue) est pleine."""
       return ... % ... == ...
   
   def defiler(file):
       """
       Retire l'élément en tête de la file circulaire.
       Renvoie le tuple formé de l'élément renvoyé et de la file une fois cet élément ôté. 
       La file est toujours implémentée sous la forme (tableau, tete, queue).
       En cas où il n'y a pas d'élément à défiler, une exception est levée avec raise et rien n'est renvoyé
       """
       tableau, tete, queue = file
       if ...:
           raise IndexError("File vide : impossible de défiler.") # Exception levée si défilement impossible
       a_retirer = ...
       ... = ...
       return ..., ...
   
   def enfiler(file, element):
       """
       Ajoute l'élément element à la file circulaire file.
       Si la file est pleine, le plus ancien élément de la file est d'abord défilé.
       Renvoie la file modifiée par cet ajout (et l'éventuelle suppression).
       """
       tableau, tete, queue = file
       if ...:
           # Défiler le plus ancien élément pour libérer de la place
           ... 
       tableau[...] = element
       ... = ...
       return ...

3. Proposer le script implémentant une file vide.

4. Tester les primitives créées avec entre autres la fonction suivante :

   def tests_file_circulaire():
       tableau = [None] * 6  # pour pouvoir stocker 5 éléments, queue pointant toujours vers une case vide ou sans sens.
       file = (tableau, 0, 0)  # File vide car ici tete = queue
       print("file actuellement vide :", file_vide(file))
       # Enfiler 4 premiers éléments
       for i in range(4):
           file = enfiler(file, 1790000000 + i*10)
       print("Après 4 enfilements :", file)  
       assert file == ([1790000000, 1790000010, 1790000020, 1790000030, None, None], 0, 4)
       print("file vide après 4 enfilements :", file_vide(file))
       print("Taille de la file :", taille(file)) 
       # Ôter les deux éléments en tête de file :
       for i in range(2):
           ote, file = defiler(file)
           print(ote, "a été enlevé de la file qui devient désormais", file)
       print("Taille de la file :", taille(file))  
       assert file == ([1790000000, 1790000010, 1790000020, 1790000030, None, None], 2, 4)
       # Vérification de la circularité correcte :
       # Enfiler 3 autres éléments pour remplit la file à 5 éléments
       for i in range(4, 7):
           file = enfiler(file, 1790000000 + i*10) 
       print("Position de la tête de la file :", file[1])    # normalement 2 (suite aux deux défilements précédents)
       print("Position de la queue de la file :", file[2])  # normalement 1 
       print("État de la file :", file)
       assert file == ([1790000060, 1790000010, 1790000020, 1790000030, 1790000040, 1790000050], 2, 1)
       print("file pleine :", est_pleine(file))
       print("Taille de la file :", taille(file)) 
       
       # Enfiler un 6è élément pour vérifier le défilement de l'élément en tête 
       print("État de la file avant l'ajout du 6è élément :", file)
       file = enfiler(file, 1790000000 + 7*10)
       print("État de la file après l'ajout du 6è élément :", file) 
       assert file == ([1790000060, 1790000070, 1790000020, 1790000030, 1790000040, 1790000050], 3, 2)
   
   tests_file_circulaire()

Partie B : Utilisation pour le bannissement temporaire d'adresses IP suspectes

1. Comme on suppose gérer en temps réels la liste logs des adresses IP, seules les adresses IP datant des 10 dernières secondes sont utiles.
   Il suffit donc de purger pour chaque adresse IP sa file associée afin de ne garder que les tentatives ayant eu lieu dans les 10000 dernières millisecondes.
   Pour cela, créer une fonction purger_file(file, temps_actuel) où temps_actuel est le timestamp en milliseconde du moment supposé de l'utilisation de la fonction, fonction qui supprime de la file les éléments datant d'il y a plus de 10000 millisecondes puis qui renvoie la file purgée.

   Attention ! Le défilement n'est possible que sur une file non vide !
   Penser à tester la fonction créée !

2. Pour gérer une liste a_bannir d'adresses IP soupçonnées d'attaque par force brute, on vous demande de mettre en place la fonction IP_a_bannir qui prend en paramètre une liste logs d'enregistrements de la forme (adresse_ip, statut, timestamp_en_ms) ainsi qu'un nombre entier timestamp_actuel qui correspond au temps du moment de l'utilisation du test et qui effectue les tâches suivantes :

   1. Créer un dictionnaire vide permettant d'associer à chaque adesse IP une file et une liste vide d'adresses IP à bannir.

   2. Regarder chaque enregistrement de logs :

      • Si on rencontre pour la première fois une adresse IP, on lui associe une file vide de la forme (tableau, tete, queue),

      • Si le statut de l'enregistrement est "échec" :

        • Si l'adresse IP est déjà bannie, passer à l'enregistrement suivant.

        • Sinon :

          • Purger la file associée à cette adresse pour ne garder que les tentatives datant d'il y a moins de 10 secondes, en utilisant l'instant actuel,

          • Rajouter à la file comme nouvel élément timestamp_en_ms,

          • Si avec cet élément la file contient 5 éléments, l'adresse IP est rajoutée à la liste des adresses IP bannies.

      • Si le statut de l'enregistrement est "succès", on réinitialise la file associée à l'adresse IP en file vide, toujours de la forme (tableau, tete, queue).

   3. Renvoyer la liste des adresses IP à bannir.

3. Tester la fonction a_bannir créée avec la fonction suivante :

   def test_IP_a_bannir():
       logs = [
           # IP 192.168.1.1 : 5 échecs en 40 ms => ATTAQUE
           ("192.168.1.1", "échec", 1790000000),
           ("192.168.1.1", "échec", 1790000010),
           ("192.168.1.1", "échec", 1790000020),
           ("192.168.1.1", "échec", 1790000030),
           ("192.168.1.1", "échec", 1790000040),
   
           # IP 192.168.1.2 : 2 échecs, succès, puis 5 échecs => ATTAQUE
           ("192.168.1.2", "échec", 1790000000),
           ("192.168.1.2", "échec", 1790000010),
           ("192.168.1.2", "succès", 1790000020),  # Réinitialisation
           ("192.168.1.2", "échec", 1790000100),
           ("192.168.1.2", "échec", 1790000110),
           ("192.168.1.2", "échec", 1790000120),
           ("192.168.1.2", "échec", 1790000130),
           ("192.168.1.2", "échec", 1790000140),
   
           # IP 192.168.1.3 : 4 échecs => PAS D'ATTAQUE
           ("192.168.1.3", "échec", 1790000000),
           ("192.168.1.3", "échec", 1790000025),
           ("192.168.1.3", "échec", 1790000050),
           ("192.168.1.3", "échec", 1790000075),
   
           # IP 192.168.1.4 : 5 échecs étalés sur 11 secondes => PAS D'ATTAQUE
           ("192.168.1.4", "échec", 1790001000),
           ("192.168.1.4", "échec", 1790003000),
           ("192.168.1.4", "échec", 1790007000),
           ("192.168.1.4", "échec", 1790008000),
           ("192.168.1.4", "échec", 17900012000),
   
           # IP 192.168.1.5 : 2 échecs, succès, puis 4 échecs, succès, puis 3 échecs => PAS D'ATTAQUE
           ("192.168.1.5", "échec", 1790000000),
           ("192.168.1.5", "échec", 1790000010),
           ("192.168.1.5", "succès", 1790000020),  # Réinitialisation
           ("192.168.1.5", "échec", 1790000100),
           ("192.168.1.5", "échec", 1790000110),
           ("192.168.1.5", "échec", 1790000120),
           ("192.168.1.5", "échec", 1790000130),    
           ("192.168.1.5", "succès", 1790000140),  # Réinitialisation
           ("192.168.1.5", "échec", 1790000150),
           ("192.168.1.5", "échec", 1790000160),
           ("192.168.1.5", "échec", 1790000170)
       ]
       assert sorted(IP_a_bannir(logs, 1790010000)) == ["192.168.1.1", "192.168.1.2"]
       print("test passé correctement")
   test_IP_a_bannir()