From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: poffice@blade.nagaokaut.ac.jp Delivered-To: poffice@blade.nagaokaut.ac.jp Received: from kankan.nagaokaut.ac.jp (kankan.nagaokaut.ac.jp [133.44.2.24]) by blade.nagaokaut.ac.jp (Postfix) with ESMTP id 2830317C1A7F for ; Wed, 18 Nov 2015 09:28:46 +0900 (JST) Received: from voscc.nagaokaut.ac.jp (voscc.nagaokaut.ac.jp [133.44.1.100]) by kankan.nagaokaut.ac.jp (Postfix) with ESMTP id 2F72BB5D8CC for ; Wed, 18 Nov 2015 09:59:21 +0900 (JST) Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by voscc.nagaokaut.ac.jp (Postfix) with ESMTP id 61E0918CC7B2 for ; Wed, 18 Nov 2015 09:59:21 +0900 (JST) Received: from [221.186.184.76] (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 3D962120498; Wed, 18 Nov 2015 09:59:20 +0900 (JST) X-Original-To: ruby-core@ruby-lang.org Delivered-To: ruby-core@ruby-lang.org Received: from o10.shared.sendgrid.net (o10.shared.sendgrid.net [173.193.132.135]) by neon.ruby-lang.org (Postfix) with ESMTPS id 4FF0C120462 for ; Wed, 18 Nov 2015 09:59:13 +0900 (JST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sendgrid.me; h=from:to:references:subject:mime-version:content-type:content-transfer-encoding:list-id; s=smtpapi; bh=Gd05iwWd20lstoSGlQGftAeTqXE=; b=OXbY3fGiUkgIQgh01A uQhCnjD/4l7QWMwzTAyH9ydcd5SMM/TDntgRMP4X3XOQlNKcQq7Y9hr+ZFoRkQQG 9AdvBte2H5u+58newptKvcvHqECYBsVj2WxmU4U9hlDxxqvbMefVv361JKRuuIvn Df+Q4otG/aRpCZ2QTnLucVLDo= Received: by filter0490p1mdw1.sendgrid.net with SMTP id filter0490p1mdw1.7714.564BCD5C3D 2015-11-18 00:59:08.898226959 +0000 UTC Received: from herokuapp.com (ec2-50-16-126-45.compute-1.amazonaws.com [50.16.126.45]) by ismtpd0006p1iad1.sendgrid.net (SG) with ESMTP id bzcH8VeeRhGIYqFXW8wpQg Wed, 18 Nov 2015 00:59:09.115 +0000 (UTC) Date: Wed, 18 Nov 2015 00:59:09 +0000 From: prijutme4ty@gmail.com To: ruby-core@ruby-lang.org Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Redmine-MailingListIntegration-Message-Ids: 46198 X-Redmine-Project: ruby-trunk X-Redmine-Issue-Id: 10984 X-Redmine-Issue-Author: olivierlacan X-Redmine-Issue-Assignee: akr X-Redmine-Sender: prijutme4ty X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-SG-EID: ync6xU2WACa70kv/Ymy4QrNMhiuLXJG8OTL2vJD1yS7RVvjFtK637QVMUATGTNp/V2ukiMIG1nu5AO VAI3hK0SLwguC4uiYnUsk8Z1JrPTYmpXk1ZBL7dnU2dToZ/AIMtbtCC/xq7jeghiShu2XgU15/eb/A iKkZv4rYBYaxjuBDJaQMJJHKPqwbdyJISqTa X-ML-Name: ruby-core X-Mail-Count: 71536 Subject: [ruby-core:71536] [Ruby trunk - Feature #10984] Hash#contain? to check whether hash contains other hash X-BeenThere: ruby-core@ruby-lang.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Ruby developers List-Id: Ruby developers List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: ruby-core-bounces@ruby-lang.org Sender: "ruby-core" Issue #10984 has been updated by Ilya Vorontsov. I've missed absence of `<=>` first. Yes, you are right. And it can slightly reduce damage. But anyway it doesn't resolve issues with misinterpretation of comparison negation. My qsort function is just the one problem which lie on surface. There are lots `if (a < b) ...; else ...` constructions in lots of codebases. I'm sure that such behaviour will lead to tons of subtle bugs. Also It's highly probable that some libraries will be subjected to malicious inputs which will cause infinite recursion bombs or other threats. Here I've slightly changed qsort code using `#reject` instead of `#select`. Not a very natural code but it's still correct: ```ruby def qsort(arr) return arr if arr.size <= 1 pivot = arr[arr.length / 2] left = arr.reject{|el| el >= pivot } right = arr.reject{|el| el <= pivot } central = arr.select{|el| el == pivot } qsort(left) + central + qsort(right) end ``` This code will not reduce size as in my previous example but contrariwise will expand array size and break asymptotical estimations of CPU time. ```ruby qsort( [{}, {a:1,b:2}, {c:3}, {a:1}, {b:2}] ) # => [{}, {:b=>2}, {:a=>1}, {:b=>2}, {:a=>1, :b=>2}, {:c=>3}, {:b=>2}, {:a=>1}, {:b=>2}, {:a=>1, :b=>2}] ``` Look at expansion rate. ```ruby qsort( 10.times.map{|i| {i => i} } ).size # => 1023 qsort( 20.times.map{|i| {i => i} } ).size # => 1048575 qsort( 25.times.map{|i| {i => i} } ).size # => 33554431 ``` The last array of 25 single-element hashes is sorted in a minute or so. It can easily hang server. Ok, I specially wrote code subjected to this attack. But in a large codebase of ruby community there would be places which have similar problems (which are not problems for totally ordered sets like numbers). It can be hard to find and exploit it, but if you did - you have broken the server. Just imagine that some code which earlies just raised an exception due to bad input now ruins your application. ---------------------------------------- Feature #10984: Hash#contain? to check whether hash contains other hash https://bugs.ruby-lang.org/issues/10984#change-54916 * Author: Olivier Lacan * Status: Closed * Priority: Normal * Assignee: Akira Tanaka ---------------------------------------- Comparing hashes seems like a common practice but there currently isn't a method to ask a hash instance whether it includes another hash instance. The most intuitive method to reach for would be `Hash#include?` but it is in fact an alias to `Hash#has_key?` What I'm looking for can be achieved with: ~~~ class Hash def contain?(other) self.merge(other) == self end end ~~~ Here's a simple demo of `#contain?` in use: ~~~ { a: true, b: false }.contain?({ a: true}) # => true { a: true, b: false }.contain?({ b: false}) # => true { a: true, b: false }.contain?({ a: false}) # => false { a: true, b: false }.contain?({ c: true}) # => false ~~~ One important note is that this method is *not checking for nested hash matches*. This may need to be addressed when the parameters include a nested hash perhaps. Thanks to Terence Lee's help, nobu created a patch for this feature last year. I've only modified the name of the method from [his original patch](https://gist.github.com/nobu/dfe8ba14a48fc949f2ed) and attached it to this issue. ---Files-------------------------------- Hash#contain_.patch (2.22 KB) -- https://bugs.ruby-lang.org/