Brechen der Data.Set-Integrität ohne GeneralizedNewtypeDeriving
Der folgende Code verwendet eine unsichereGeneralizedNewtypeDeriving Verlängerung zu brechenData.Set durch Einfügen verschiedener Elemente mit unterschiedlichenOrd Instanzen:
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
import Data.Set
import System.Random
class AlaInt i where
fromIntSet :: Set Integer -> Set i
toIntSet :: Set i -> Set Integer
instance AlaInt Integer where
fromIntSet = id
toIntSet = id
newtype I = I Integer deriving (Eq, Show, AlaInt)
instance Ord I where compare (I n1) (I n2) = compare n2 n1 -- sic!
insert' :: Integer -> Set Integer -> Set Integer
insert' n s = toIntSet $ insert (I n) $ fromIntSet s
randomInput = take 5000 $ zip (randomRs (0,9) gen) (randoms gen) where
gen = mkStdGen 911
createSet = Prelude.foldr f empty where
f (e,True) = insert e
f (e,False) = insert' e
main = print $ toAscList $ createSet randomInput
Der Code wird gedruckt[1,3,5,7,8,6,9,6,4,2,0,9]. Beachten Sie, dass die Liste ungeordnet ist und hat9 zweimal.
Ist es möglich, diesen Dictionary-Swap-Angriff mit anderen Erweiterungen durchzuführen, z.ConstraintKinds? Wenn ja, kannData.Set umgestaltet werden, um solchen Angriffen standzuhalten?