18

以下のコードは、安全でないGeneralizedNewtypeDeriving拡張機能を使用して、異なるインスタンスData.Setを持つ異なる要素を挿入することで中断しています。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

コードが出力され[1,3,5,7,8,6,9,6,4,2,0,9]ます。リストは順不同で、92 回あることに注意してください。

他の拡張機能を使用してこの辞書スワッピング攻撃を実行することは可能ConstraintKindsですか? はいの場合、Data.Setそのような攻撃に耐えられるように再設計できますか?

4

1 に答える 1

21

これは重要な質問だと思うので、他の場所からの回答を繰り返します。Haskell98 では、拡張機能をまったく使用せずに、同じ型に対して同じクラスのインスタンスを複数持つことができます。

$ 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]

はい、辞書を内部に保存することで、この種の攻撃を防ぐことができます。

data MSet a where MSet :: Ord a => Set a -> MSet a
于 2012-10-05T10:44:31.870 に答える