打破Data.Set诚信没有GeneralizedNewtypeDeriving [英] Breaking Data.Set integrity without GeneralizedNewtypeDeriving

问题描述

下面的代码使用不安全的 GeneralizedNewtypeDeriving 扩展通过插入具有不同<<$的不同元素来打破 Data.Set c $ c> Ord 实例：

The code below uses an unsafe GeneralizedNewtypeDeriving extension to break Data.Set by inserting different elements with different Ord instances:

{-# 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 两次。

The code prints [1,3,5,7,8,6,9,6,4,2,0,9]. Note that the list is unordered and has 9 twice.

是否可以使用其他字典交换攻击扩展，例如 ConstraintKinds ？如果是的话，是否可以重新设计 Data.Set 以抵御这种攻击？

Is it possible to perform this dictionary swapping attack using other extensions, e.g. ConstraintKinds? If yes, can Data.Set be redesigned to be resilient to such attacks?

推荐答案

我认为这是一个重要的问题，所以我会在其他地方重复我的答案：在Haskell98中可以有相同类的多个实例，而没有任何扩展：

I think that's an important question, so I'll repeat my answer from elsewhere: you can have multiple instances of the same class for the same type in Haskell98 without any extensions at all:

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

是的，您可以防止这种类型通过在内部存储字典来进行攻击：

And yes, you can prevent this kind of attacks by storing the dictionary internally:

data MSet a where MSet :: Ord a => Set a -> MSet a

这篇关于打破Data.Set诚信没有GeneralizedNewtypeDeriving的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！