Lorsque vous travaillez sur un grand projet logiciel, j'utilise souvent des tests Fuzz dans le cadre de mes cas de test pour aider à fumer des bogues qui ne peuvent apparaître que lorsque l'entrée atteint une certaine taille ou forme. Je fais cela le plus souvent en utilisant simplement les installations de numéro aléatoire standard fournies avec le langage de programmation que je devais utiliser.
Récemment, j'ai commencé à me demander, en ignorant les avantages ou les inconvénients des tests de Fuzz en général, qu'il soit une bonne idée d'utiliser des générateurs de nombre de pseudo-pseudorandom non cryptocycliques lors du test Fuzz. Les générateurs de nombres aléatoires faibles présentent souvent des modèles qui les distinguent de véritables séquences aléatoires, même si ces modèles ne sont pas évidents. Il semble que un test de fuzz utilisant un PRNA faible pourrait toujours ne pas déclencher certains bugs latents qui ne se présentent que dans certaines circonstances, car les numéros de pseudo-poste pourraient être liés les uns aux autres d'une manière qui ne déclenche jamais ces circonstances.
est-il intrinsèquement imprudent d'utiliser un PRNA faible pour les tests de fuzz? S'il est théoriquement non sain de le faire, est-il toujours raisonnable dans la pratique?
3 Réponses :
Je ne pense pas que ça compte vraiment, mais je ne peux pas le prouver.
Le test Fuzz n'essaiera que des intrants, dans la plupart des cas une proportion de minuscules des possibilités. Quelle que soit la qualité que vous utilisez, il peut ou non trouver l'une des entrées qui enfreint votre code, en fonction de la proportion de toutes les entrées possibles rompt votre code. Sauf si le modèle du PRNG n'est très simple, il me semble improbable qu'il correspond à un motif dans les entrées «mauvaises» que vous recherchez, de sorte que cela ne frappera ni plus ni moins de vrai aléatoire.
En fait, si vous saviez comment choisir un RNG de maximiser la probabilité de trouver des entrées mauvaises, vous pouvez probablement utiliser cette connaissance pour vous aider à trouver le bogue plus directement ...
Je ne pense pas que vous devriez utiliser un vraiment mauvais prng. Ce n'est généralement pas si difficile dans une langue donnée pour trouver Crypto ou au moins des bibliothèques de hasch. SHA-1 est partout et facile à utiliser pour générer un flux ou faire échouer que RC4 est trivial de mettre en œuvre vous-même. Les deux offrent un très bon PRNG, sinon aussi sécurisé comme Shum Blum Shub. J'aurais pensé que la principale préoccupation est la vitesse - si, par exemple, une Mersenne Twister peut générer des cas de test Fuzz 10 fois plus rapides, et le code sous test est raisonnablement rapide, il pourrait avoir une meilleure chance de trouver de mauvaises intrants dans une donnée donnée. Temps indépendamment du fait que, donnant 624 sorties, vous pouvez déduire l'état complet du RNG ... rand par exemple est autorisé à présenter des modèles très simples, tels que le LSB alternant. Et si votre code utilise un PRNG en interne, vous souhaitez probablement éviter d'utiliser le même PRNG de la même manière dans le test, juste pour vous assurer de ne pas passer accidentellement les cas de test que les données d'entrée correspondent au flux de numéros généré par l'intérieur! Bien sûr, car vous espérez qu'ils utiliseront différentes graines, mais toujours.
Vous confondez deux grades très différentes de "faiblesse":
Je comprends donc ce que vous dites, mais je suis toujours un peu confus. Si vous avez quelque chose de statistiquement mais pas cryptographiquement aléatoire, le fait que les termes futurs de la production puissent être prédits à partir des termes précédents signifient que certaines séquences de fuzz possibles ne pouvaient pas être générées? Je suppose que ce que je pense ici, c'est que si la sortie est en quelque sorte prévisible des termes précédents, la séquence fuzz générée n'est pas "assez aléatoire". Je manque probablement quelque chose depuis ce que vous dites a du sens, mais je ne peux pas me convaincre de la distinction.
@Templatetypedef: Les PRNs cryptographiquement forts sont tout aussi prévisibles si vous connaissez leur graine. La différence est que c'est la chose seulement qui vous permet de prédire la sortie.
Je comprends, mais ma question est que si si des PRNG aléatoires statistiquement peuvent avoir leurs prochaines sorties prédites à partir de leurs sorties précédentes, cela signifie-t-il que certaines séquences aléatoires ne pouvaient pas générer (depuis une séquence particulière de sorties, les éléments suivants Les sorties seraient corrigées?)
@TemplatetypeDef: Ce que vous dites est vrai aussi de PRNG cryptographiquement. Par exemple, considérez RC4 (qui est certes un peu brisé). Il a 256! Etats internes possibles, qui est 2 ^ 1684. Si la période a la période n, il y a 256 ^ N différentes séquences N-Byte que vous pourriez espérer de sortir. Je ne connais pas la période de RC4, mais c'est beaucoup plus de 200 personnes, donc clairement qu'il ne leur rend pas tous. Une analyse similaire s'appliquera à la taille de l'état et à la période de tout PRNG qui est bonne, car elle aura une période colossale. Il suffit de choisir une grande taille, il ne produira pas toutes les séquences qui grandissent.
Donc, si vous utilisez N octets de données "aléatoires" pour construire un étui de test Fuzz, vous avez certainement besoin d'un PRNG avec au moins N octets d'état interne si vous voulez que toutes les entrées potentielles soient possibles. C'est vrai quelle que soit la sécurité cryptographique. Notez que la sécurité cryptographique n'est pas (pour la plupart des PRNG) une propriété de l'algorithme, c'est une déclaration de notre propre ignorance sur l'algorithme. Blum Blum Shub est inhabituel en ce sens qu'elle a une preuve plutôt forte de l'imprévisibilité - en disant que c'est cryptographiquement sécurisé, c'est une déclaration de notre ignorance sur laquelle les chiffres sont rapidement.
Vous n'avez pas besoin de source imprévisible (c'est exactement ce qu'un générateur cryptographiquement sécurisé est), vous n'avez besoin que d'une source avec de bonnes propriétés statistiques.
Ainsi, l'utilisation d'un générateur général est suffisante - il est rapide et généralement reproductible (ce qui signifie que les problèmes sont également reproductables).