security haskell type-safety language-extension

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