security - Rompiendo datos. Establece la integridad sin el uso generalizado.
haskell type-safety (1)
El código a continuación utiliza una extensión no segura GeneralizedNewtypeDeriving
para romper Data.Set
insertando diferentes elementos con diferentes instancias de Ord
:
{-# 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
El código se imprime [1,3,5,7,8,6,9,6,4,2,0,9]
. Tenga en cuenta que la lista no está ordenada y tiene 9
dos veces.
¿Es posible realizar este ataque de intercambio de diccionario utilizando otras extensiones, por ejemplo, ConstraintKinds
? En caso afirmativo, ¿se puede rediseñar Data.Set
para que sea resistente a tales ataques?
Creo que esa es una pregunta importante, así que repetiré mi respuesta desde otro lugar: puedes tener múltiples instancias de la misma clase para el mismo tipo en Haskell98 sin ninguna extensión:
$ cat A.hs
module A where
data U = X | Y deriving (Eq, Show)
$ cat B.hs
module B where
import Data.Set
import A
instance Ord U where
compare X X = EQ
compare X Y = LT
compare Y X = GT
compare Y Y = EQ
ins :: U -> Set U -> Set U
ins = insert
$ cat C.hs
module C where
import Data.Set
import A
instance Ord U where
compare X X = EQ
compare X Y = GT
compare Y X = LT
compare Y Y = EQ
ins'' :: U -> Set U -> Set U
ins'' = insert
$ cat D.hs
module D where
import Data.Set
import A
import B
import C
test = ins'' X $ ins X $ ins Y $ empty
$ ghci D.hs
Prelude D> test
fromList [X,Y,X]
Y sí, puede evitar este tipo de ataques almacenando el diccionario internamente:
data MSet a where MSet :: Ord a => Set a -> MSet a