在没有GeneralizedNewtypeDeriving的情况下破坏Data.Set完整性
在没有GeneralizedNewtypeDeriving的情况下破坏Data.Set完整性
提问于 2012-10-05 04:23:12
下面的代码使用不安全的GeneralizedNewtypeDeriving扩展通过插入具有不同Ord实例的不同元素来中断Data.Set：
{-# 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]。请注意，该列表是无序的，并且有两次9。
是否可以使用其他扩展来执行此字典交换攻击，例如ConstraintKinds？如果是，是否可以将Data.Set重新设计为具有抵御此类攻击的能力？
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-10-05 18:44:32
我认为这是一个重要的问题，所以我将在其他地方重复我的答案:在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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12735274
复制相关文章
相似问题