From patchwork Mon Nov 18 14:20:20 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Hurukawa2121 X-Patchwork-Id: 3947 Return-Path: Delivered-To: patchwork@openvpn.net Received: by 2002:a05:7000:1ee:b0:5d9:9f4c:3bc7 with SMTP id 14csp2669395map; Mon, 18 Nov 2024 06:24:12 -0800 (PST) X-Forwarded-Encrypted: i=2; AJvYcCXCE/GnYDjgTvNTCiXRyZEwKy7p4WHTHAkAjJb7ZWtTTvlX/xkQfmHztVYTIRj6mOuW5cyaL05TzHQ=@openvpn.net X-Google-Smtp-Source: AGHT+IHF9bnkqRSWSXcCr/DO0Chx9jgWcFlcAYXFNcu5hd5ut49yxZDIODSuKQINjquro+7JtXli X-Received: by 2002:a05:6602:140f:b0:83a:b43b:da89 with SMTP id ca18e2360f4ac-83e6c319858mr1162444239f.10.1731939852119; Mon, 18 Nov 2024 06:24:12 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1731939852; cv=none; d=google.com; s=arc-20240605; b=S1dcs/1e2TS98ZrDiqDD/ayFDhxogwu6wjC3oRDU4+UIYewpTD1Y/34VWjoT2SP0l1 WzV5McNwLeN8VW08XuTdR9WOmjUPfXDRejaptNpUo91aNMV0kofJpJVSUiNCvf0mgCbu VL0RH9QYbcz+6P15eywLhGpRVj01y/wNBQa++8aKTyPHBLRHt4knd5lcCejSIM1rv+eQ DRffKN5HzMOxa684QooP2lKQ0xt1sJXNH8vst8hrhoabI5ZwANp0CnHbwyZaZ9AFSy5d jhhOzJkldBYCh30aVhZw+1AtJaZlUakLfDy83aYhOX1a1SEYfs7DUpYfe6CZmLXKehu/ r3aQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=errors-to:content-transfer-encoding:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence:subject :mime-version:message-id:date:to:from:dkim-signature:dkim-signature :dkim-signature; bh=ttDkmISqS7084PbXgfnyXgW5qoh/SHis4oUtrp72dGc=; fh=4NbAC/LsuMLI0S0hprUlLSLCiHwg6SCAifhH718Jh0Q=; b=Hc7J03g/YNTAQcPM98YRKlh3HSzrjhvMYwPy83KSeZPJJ62aDL7XhKsVo/tKwGy/qH UnHZKbAABhXvsATm4VXXlrlAdHvVdwY1fT43NfO0XUFmNaUdTof10SHaQmMy2MAFjE+Q 1egRd5Z7G5xKhaKAhUb+Fzbk1iHIQv490kKb2ldRHB2kVBNSrdsQXHYHLU5n5Aib17DS ++UEr1Mqok57drEo2Y+BHTyxH0VtMP5vIiELJpuP31nsPTvhgmjP8PJdZVbX/UpqIdQj Ht5quh67WavneG7p7/xkrvwWQlbSjB9ILq7BKJNYyf9Zm3wryk/VjNRGUM4UwPhTMvtU bv9Q==; dara=google.com ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@sourceforge.net header.s=x header.b=EdEXiKOe; dkim=neutral (body hash did not verify) header.i=@sf.net header.s=x header.b="JM7/bGRo"; dkim=neutral (body hash did not verify) header.i=@gmail.com header.s=20230601 header.b=Qs6RNUuR; spf=pass (google.com: domain of openvpn-devel-bounces@lists.sourceforge.net designates 216.105.38.7 as permitted sender) smtp.mailfrom=openvpn-devel-bounces@lists.sourceforge.net; dmarc=fail (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=fail header.i=@openvpn.net Received: from lists.sourceforge.net (lists.sourceforge.net. [216.105.38.7]) by mx.google.com with ESMTPS id 8926c6da1cb9f-4e06d6dbe11si4390830173.16.2024.11.18.06.24.11 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 18 Nov 2024 06:24:12 -0800 (PST) Received-SPF: pass (google.com: domain of openvpn-devel-bounces@lists.sourceforge.net designates 216.105.38.7 as permitted sender) client-ip=216.105.38.7; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@sourceforge.net header.s=x header.b=EdEXiKOe; dkim=neutral (body hash did not verify) header.i=@sf.net header.s=x header.b="JM7/bGRo"; dkim=neutral (body hash did not verify) header.i=@gmail.com header.s=20230601 header.b=Qs6RNUuR; spf=pass (google.com: domain of openvpn-devel-bounces@lists.sourceforge.net designates 216.105.38.7 as permitted sender) smtp.mailfrom=openvpn-devel-bounces@lists.sourceforge.net; dmarc=fail (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=fail header.i=@openvpn.net Received: from [127.0.0.1] (helo=sfs-ml-1.v29.lw.sourceforge.com) by sfs-ml-1.v29.lw.sourceforge.com with esmtp (Exim 4.95) (envelope-from ) id 1tD2fY-0006GN-0e; Mon, 18 Nov 2024 14:24:00 +0000 Received: from [172.30.29.66] (helo=mx.sourceforge.net) by sfs-ml-1.v29.lw.sourceforge.com with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1tD2fR-0006GC-7x for openvpn-devel@lists.sourceforge.net; Mon, 18 Nov 2024 14:23:53 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=sourceforge.net; s=x; h=Content-Transfer-Encoding:MIME-Version:Message-Id: Date:Subject:Cc:To:From:Sender:Reply-To:Content-Type:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=x/ALYeIzGz6XKih5OGcl/3tm9PZLshDhgjmWCI/6lis=; b=EdEXiKOeAuuleq4WO4r5x0wuDB SlHP0ncf4ttj3hEYdiH3lxJuNFtNwqUGTCHJvpyMSx1Bfhs8K01Zm5BJuXNtZt9D9qAj9QaxO4y+J utOMjhSACbTD7qjnBhG1GWmqMrElbXnPHyeYFC6mTaoigQsLQWh8vaBdHgN0A1NbBQpQ=; DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=sf.net; s=x ; h=Content-Transfer-Encoding:MIME-Version:Message-Id:Date:Subject:Cc:To:From :Sender:Reply-To:Content-Type:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To: References:List-Id:List-Help:List-Unsubscribe:List-Subscribe:List-Post: List-Owner:List-Archive; bh=x/ALYeIzGz6XKih5OGcl/3tm9PZLshDhgjmWCI/6lis=; b=J M7/bGRoay4UGpQdBD0+TpR4T887Iu4zcN0mG8wgvDvfmT1iwry6obBc8wUbzUyijOk1EXTuTYLeJl sB05kIe9eyWCdl8SH3I9ke1vPU1vvMn+uKf/MZG9RHzuvd63GqTCVUSYWku1paP3X+ISe3XH9S8Fu +vStUJcXR9SV3h3A=; Received: from mail-pl1-f169.google.com ([209.85.214.169]) by sfi-mx-2.v28.lw.sourceforge.com with esmtps (TLS1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (Exim 4.95) id 1tD2fP-00073p-Ms for openvpn-devel@lists.sourceforge.net; Mon, 18 Nov 2024 14:23:52 +0000 Received: by mail-pl1-f169.google.com with SMTP id d9443c01a7336-20cb47387ceso42749955ad.1 for ; Mon, 18 Nov 2024 06:23:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731939821; x=1732544621; darn=lists.sourceforge.net; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=x/ALYeIzGz6XKih5OGcl/3tm9PZLshDhgjmWCI/6lis=; b=Qs6RNUuRkoZPf3NK7xK8n0LmTmlqs2GedaOVUwPClHpCrMnUh2O1QwfBQXG0P1MROf 8woIIeqsccfm/eNMB1SSAf2jvanTczqmPa1oEF+t0oMai6yAVIvt6rNqLGyfKjsf57jk aRqVAi8piyhFwatHLE4aVaHVg0Av+gRaYYmWq74AMA7l96RJ75hlAdRjEjgHhdHJ11gP TpVsK8pX3Vsy5nIsTTILkHOYgh6onSieLDCbOApn0qJgwQ0C1uO656URvvGlU7DwQ4AX twno0Dws6LfKWAliC/plJuDPgL3OmIHI00Z38YhzehxFLs1lMrbGCAoaJOWFxMDbiSeN FMqA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731939821; x=1732544621; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=x/ALYeIzGz6XKih5OGcl/3tm9PZLshDhgjmWCI/6lis=; b=ZEwb3lttlhQbXyMkRRJy6Xvdr3n2s3Em7C+h8pCCaFUxP2fKaM0iVb3WMvmhy7nyW+ cF8FcOvQGZ6IF747nDSMEigAN1J/3cPnBdfJZSpkTUxkmYKrPvGJAXBB5f/n5wJl5+3j eJ0KSheHEEolENi31supyGjHzrPqAOXSI7yWLBEBxh8iXoZgq/u3Y8t6Eo6C2PShEmSp x+YZJFZZxTW3IR2K9MznkzA4JeWqOWPzzP3qR+5ScENu8HGRAFiut03HzrgSObaCAlKa C0LucmJl54bvSWoPaNCK97uJ1pL81xIJXrHdS5gvDO2r2pld8yYRkplk0PHicqgodjMz hHxQ== X-Gm-Message-State: AOJu0YwhCCgnt8tBVDBda6alKURlktLBZ1CImuJdItiyYu6Xch7gmi/8 dQGjidondV0k+3B0a7jvmzUGD0k2IwbauNqu0nwj5m3DfP7EaUwjfX7n2Q== X-Received: by 2002:a17:902:da8e:b0:211:e812:3948 with SMTP id d9443c01a7336-211e8128848mr152241465ad.0.1731939820848; Mon, 18 Nov 2024 06:23:40 -0800 (PST) Received: from localhost.localdomain ([2001:268:9872:7d79:e1ed:23b4:3ace:99fd]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2eaa5e0ee07sm132840a91.11.2024.11.18.06.23.39 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 18 Nov 2024 06:23:40 -0800 (PST) From: Hurukawa2121 To: openvpn-devel@lists.sourceforge.net Date: Mon, 18 Nov 2024 23:20:20 +0900 Message-Id: <20241118142019.31045-1-shujifurukawa1213@gmail.com> X-Mailer: git-send-email 2.39.3 (Apple Git-146) MIME-Version: 1.0 X-Spam-Score: 0.1 (/) X-Spam-Report: Spam detection software, running on the system "util-spamd-2.v13.lw.sourceforge.com", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: --- Improve shuffling algorithm of connection list This patch implements the Fisher-Yates shuffle algorithm to ensure that all permutations of the connection target list are generated with equal probability, eliminating biases present in the previous [...] Content analysis details: (0.1 points, 6.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [209.85.214.169 listed in list.dnswl.org] 0.0 RCVD_IN_VALIDITY_RPBL_BLOCKED RBL: ADMINISTRATOR NOTICE: The query to Validity was blocked. See https://knowledge.validity.com/hc/en-us/articles/20961730681243 for more information. [209.85.214.169 listed in bl.score.senderscore.com] 0.0 RCVD_IN_VALIDITY_CERTIFIED_BLOCKED RBL: ADMINISTRATOR NOTICE: The query to Validity was blocked. See https://knowledge.validity.com/hc/en-us/articles/20961730681243 for more information. [209.85.214.169 listed in sa-accredit.habeas.com] 0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in digit [shujifurukawa1213[at]gmail.com] 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record -0.0 SPF_PASS SPF: sender matches SPF record 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider [shujifurukawa1213[at]gmail.com] 0.0 RCVD_IN_MSPIKE_H3 RBL: Good reputation (+3) [209.85.214.169 listed in wl.mailspike.net] -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature -0.1 DKIM_VALID_EF Message has a valid DKIM or DK signature from envelope-from domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid 0.0 RCVD_IN_MSPIKE_WL Mailspike good senders X-Headers-End: 1tD2fP-00073p-Ms Subject: [Openvpn-devel] [PATCH v2] Improve shuffling algorithm of connection list X-BeenThere: openvpn-devel@lists.sourceforge.net X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: openvpn-devel-bounces@lists.sourceforge.net X-getmail-retrieved-from-mailbox: Inbox X-GMAIL-THRID: =?utf-8?q?1816070562381312329?= X-GMAIL-MSGID: =?utf-8?q?1816070562381312329?= --- Improve shuffling algorithm of connection list This patch implements the Fisher-Yates shuffle algorithm to ensure that all permutations of the connection target list are generated with equal probability, eliminating biases present in the previous shuffling method. In the Fisher-Yates algorithm, there's only one way to obtain each permutation through a series of element swaps, so all permutations occur with equal probability in theory. Signed-off-by: Shuji Furukawa src/openvpn/init.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) Acked-by: Antonio Quartulli diff --git a/src/openvpn/init.c b/src/openvpn/init.c index 9371024e..c4fb5cd7 100644 --- a/src/openvpn/init.c +++ b/src/openvpn/init.c @@ -467,7 +467,14 @@ ce_management_query_remote(struct context *c) #endif /* ENABLE_MANAGEMENT */ /* - * Initialize and possibly randomize connection list. + * Initialize and randomize the connection list. + * + * Applies the Fisher-Yates shuffle algorithm to ensure all permutations are equally probable, + * thereby eliminating shuffling bias in the previous method. + * + * The algorithm randomly selects an element from the unshuffled portion and places it at position i. + * There's only one way to obtain each permutation through these swaps. + * This guarantees that each permutation occurs with equal probability in theory. */ static void init_connection_list(struct context *c) @@ -478,9 +485,9 @@ init_connection_list(struct context *c) if (c->options.remote_random) { int i; - for (i = 0; i < l->len; ++i) + for (i = l->len - 1; i > 0; --i) { - const int j = get_random() % l->len; + const int j = get_random() % (i + 1); if (i != j) { struct connection_entry *tmp;