Aeson Object Design (Part 3)

In discussing the Aeson Object design, I pointed out that using a [(Text, Value)] representation could even help with mitigation of the denial-of-service vulnerability that is currently being addressed:

In some cases, it would even be possible to use the list (better than Vector for conversion) length to mitigate attacks. For example, consider an API that uses 10 properties. If the length of the list is above a certain threshold (10 for a strict API), an error could be returned. Otherwise, the HashMap could be constructed and used as usual. This would allow users to mitigate attacks while keeping the performance of HashMap, with only the additional cost of determining the length of the list (one time O(n)).

I wrote O(n) at the end, but note that the n here is the threshold, not the length of the list. We only need to count up to the threshold to determine the result of the predicate; there is no need to compute the actual length of the list.

This function is usually called lengthExceeds, and Hoogle makes it easy to see which packages define it.

Henning Thielemann’s utility-ht utility library includes the following functions, implemented using drop:

• lengthAtLeast: length xs >= n
• lengthAtMost: length xs <= n

The lengthExceeds function could be implemented as not . lengthAtMost.

The hedgehog testing library includes the following function, also implemented using drop:

• atLeast: length xs >= n

I prefer Henning’s implementation, which uses n <= 0 instead of n == 0.

The following functions are included in ghc:

• lengthAtLeast: length xs >= n
• lengthAtMost: length xs <= n
• lengthExceeds: length xs > n
• lengthIsNot: length xs /= n
• lengthIs: length xs == n
• lengthLessThan: length xs < n

These functions are implemented the following function, not drop:

atLength
    :: ([a] -> b)   -- Called when length ls >= n, passed (drop n ls)
                    --    NB: arg passed to this function may be []
    -> b            -- Called when length ls <  n
    -> [a]
    -> Int
    -> b

Implementing this function using a tail-recursive helper function would be a good exercise for somebody learning Haskell!

If Aeson were to use the list representation of Object, a lengthExceeds function could be added to Aeson so that additional dependencies are not required.

-- | Check if a list is longer than the specified length
--
-- (lengthExceeds n xs) = (length xs > n)
lengthExceeds :: Int -> [a] -> Bool
lengthExceeds n
    | n < 0     = const False
    | otherwise = not . null . drop n

Such a function could be used with when and fail to return an error when there are too many entries, as follows:

when (lengthExceeds 2 entries) $ fail "Coord object has too many properties"

In the common case where the entry list is only used for this check before constructing as HashMap, a helper function can be used.

withMaxLength
  :: Int
  -> (ObjectEntries -> Parser a)
  -> ObjectEntries
  -> Parser a
withMaxLength n f entries = do
    when (lengthExceeds n entries) $ fail "object has too many properties"
    f entries

The example instance definition could be written to use this function to mitigate attacks as follows:

instance FromJSON Coord where
  parseJSON = withObjectEntries "Coord" . withMaxLength 2 . asHashMap $
    \v -> Coord
      <$> v .: "x"
      <*> v .: "y"

With this implementation, the error message is not very helpful. Sometimes is is preferred to not give helpful error messages when dealing with security issues, because helpful error messages help attackers. In cases where a more helpful error message is desired, however, a function like the following may be preferred to handle the common case:

withObjectOfMaxLength
  :: String
  -> Int
  -> (HashMap Text Value -> Parser a)
  -> Value
  -> Parser a

This function checks that the value is an object, makes sure that the object does not have too many properties, and constructs the HashMap. It can be used as follows:

example = withObjectOfMaxLength "Coord" 2 $ \v -> Coord
    <$> v .: "x"
    <*> v .: "y"

This demonstrates how the design can be used to mitigate the denial-of-service attack and still provide the performance of HashMap.