Slice Distance: An Insert-Only Levenshtein Distance with a Focus on Security Applications

Afzal, Zeeshan,1991-Karlstads universitet,Institutionen för matematik och datavetenskap (from 2013),PRISEC (författare)

Slice Distance : An Insert-Only Levenshtein Distance with a Focus on Security Applications

Levenshtein distance is well known for its use in comparing two strings for similarity. However, the set of considered edit operations used when comparing can be reduced in a number of situations. In such cases, the application of the generic Levenshtein distance can result in degraded detection and computational performance. Other metrics in the literature enable limiting the considered edit operations to a smaller subset. However, the possibility where a difference can only result from deleted bytes is not yet explored. To this end, we propose an insert-only variation of the Levenshtein distance to enable comparison of two strings for the case in which differences occur only because of missing bytes. The proposed distance metric is named slice distance and is formally presented and its computational complexity is discussed. We also provide a discussion of the potential security applications of the slice distance.

Garcia, Johan,1970-Karlstads universitet,Institutionen för matematik och datavetenskap (from 2013),DISCO(Swepub:kau)johagarc (författare)
Lindskog, Stefan,1967-Karlstads universitet,Institutionen för matematik och datavetenskap (from 2013),PRISEC(Swepub:kau)steflind (författare)
Brunström, Anna,1967-Karlstads universitet,Institutionen för matematik och datavetenskap (from 2013),DISCO(Swepub:kau)annabrun (författare)
Karlstads universitetInstitutionen för matematik och datavetenskap (from 2013) (creator_code:org_t)

Ingår i:Proceedings of NTMS 2018 Conference and WorkshopNew York : IEEE, s. 1-597815386366269781538636633

Av författaren/redakt...: Afzal, Zeeshan, ...; Garcia, Johan, 1 ...; Lindskog, Stefan ...; Brunström, Anna, ...

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.