Les tests de pénétration sont une méthodologie pour évaluer la sécurité d'un réseau en générant et exécutant de possibles attaques informatiques. Automatiser cette tâche permet de réaliser des tests réguliers et systématiques. Une question clef est : "Comment générer ces attaques ?" Ce problème se formule naturellement comme de la planification dans l'incertain, plus précisément avec une connaissance incomplète de la configuration du réseau. Les travaux antérieurs emploient de la planification classique, et requièrent de coûteux pré-traitements réduisant cette incertitude par l'application extensive de méthodes de scan. Au contraire, nous modélisons ici le problème de la planification d'attaques à travers des processus de décision markoviens partiellement observables (POMDP). Ceci nous permet de raisonner à propos de la connaissance disponible, et d'employer intelligemment les actions de scan comme faisant partie de l'attaque. Comme on s'y attendrait, cette solution précise ne passe pas à l'échelle. Nous concevons donc une méthode qui repose sur les POMDP pour trouver de bonnes attaques sur des machines individuelles, lesquelles sont recomposées en une attaque sur le réseau complet. Cette décomposition exploite la structure du réseau dans la mesure du possible, faisant des approximations ciblées (seulement) où cela est nécessaire. En évaluant cette méthode sur un jeu de tests industriels adaptés convenablement, nous démontrons son efficacité à la fois en temps de calcul et en qualité de la solution.