Recentemente, mi sono interessato alla crittografia applicata e sono incappato in un link che spiega come le stime di Linux entropia .
Ad un certo punto, ci viene detto che la stima dell'entropia è basata sulla prima, seconda e terza differenza dei timestamp di determinati eventi di sistema. Giusto. Quello che non ho capito è stata l'intuizione dietro a questo, spiegato nel link come segue:
This use of deltas is approximately the same as attempting to fit an n degree polynomial to the previous n+1 points, then looking to see how far the new point is from the best prediction based on the previous n points. The minimum of the deltas is used, which has the effect of taking the best fit of a 0th, 1st or 2nd degree polynomial, and using that one.
Per chiarire, ecco cosa (penso) ho capito. Prendendo l'esempio degli eventi del mouse nel link:
Mouse event times 1004 1012 1024 1025 1030 1041
1st differences 8 12 1 5 11
2nd differences 4 11 4 6
3rd differences 7 7 2
Adatta un polinomio di grado n ai precedenti punti n + 1: immagino che prenderebbe il (i + 1) -th diff, che sono le prime diff di i-es. diff . Questi potrebbero essere usati per prevedere i prossimi valori dell'i-es diff, da qui il 'fitting'. Per esempio. il primo diff spiega come cambiano i valori consecutivi della linea di eventi del mouse (differenza 0).
Quanto è lontano il nuovo punto dalla migliore previsione basata sui precedenti n punti: Suppongo che questo sia dato da (i + 2) -th diff? Per esempio. dopo l'ultimo evento del mouse, 1041, il secondo diff è 6, che è quanto lontano 1041 ( il nuovo punto ) è da 1035 ( la migliore previsione ). La predizione si ottiene prendendo il precedente valore di 0th diff, 1030, aggiunto al precedente valore di diff 1, 5.
Uso del delta minimo: La mia ipotesi migliore è che lo stimatore di entropia scelga il valore minimo, poiché è la soluzione migliore per (i-1) -th diff (o (i-1) polinomiale di terzo grado). Penso di capire in che modo questo metodo si adatta al meglio, ma in realtà non ho ottenuto il "perché".
I miei dubbi / domande sono:
- Potrei trascurare qualcosa di ovvio, ma non vedo ancora la relazione tra la mia idea di adattamento polinomiale di grado n (ad esempio regressione polinomiale usando un metodo dei minimi quadrati).
- Qual è la vera motivazione alla base della scelta del delta minimo? Perché fornisce una buona misura di quanto sia inaspettato il prossimo punto dati? È perché il delta minimo è il più conservatore?