cpython
cpython copied to clipboard
python
gh-136061: IDLE - update code in editor.Editor.load_extension
A DOS by Quadratic complexity issue is fixed in idlelib. Part of (but does not fix) #134873.
- Issue: gh-134873
- Issue: gh-136061
I believe that the 6 lines from 1205 to 1210 can be replaced by 2 lines -- an re.match and an f-string. I will submit an alternate proposal later. I believe that the input vevent name should have either no <>s or 2 of each, with maybe the latter for back compatibility (I will test). But I will may stick with the more general code to not break buggy extensions.
@terryjreedy so should I leave the code for now, or should I go ahead and replace with the re.match thing you are going to propose?
@ZeroIntensity so do you mean that active voice is preferred in release notes? I can replace this specific case with the change that you are suggesting, but I'm asking for advice in this aspect for future News.
@johnzhou721 I would greatly appreciate it if you could kindly address the issue located at https://github.com/python/cpython/blob/5ab66a882d1b5e44ec50b25df116ab209d65863f/Lib/idlelib/editor.py#L1373-L1378. I sincerely apologize for overlooking this in my previous message.
As an example, I successfully utilized Gemini 2.5 Pro to generate a reasonable fix for this problem. Could you give it a try?
@kexinoh Yes, I would give it a try once I have time; however, I am working on something else right now -- is it acceptable if I delay this by about a day or so?
(if anyone else has a fix ready before I get to this, feel free to make a pr onto the branch of my pr and I'll merge it into my PR)
@kexinoh I have a small amount of time not enough to work on anything else before I end my day so I attempted the issue you pointed out -- but can't test though.
Assuming this is the fix that we go with, let's add a test case.
Where? How? For what? Thanks! @ZeroIntensity
Where? How? For what?
We need a test case in test_idlelib that results in DOS/extreme slowness off main. Basically, just do something to prove that this PR fixes it (probably just testing with large amounts of data).
A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.
Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.
![bedevere-app[bot] avatar](https://avatars.githubusercontent.com/in/388350?v=4 "Published by a pub.dev verified publisher"){kind=small}
Good. Very good.
I've found that I've been assuming everything has width of tabwidth... I'd need to change my approach significantly.
OK So I've just made the tests run in an more organized way, and I've also asserted an at least 10x speedup (w/ one of the test of 10^4 order of magnitude length) and I've also used the old code to confirm the test data is correct. Looks good to me so far!
I've fixed the issues -- is macOS 14 not using --slow-ci?
Anyways, I just scrubbed the ncharsdeleted stuff in the function and calculate it manually using length differences.
@bedevere-bot I have made the requested changes, please review again
Thanks for making the requested changes!
@picnixz: please review the changes made to this pull request.
Sidenote: I have a very hard time believing that there is any reasonable DOS in this code at all. Can someone please explain how it can be exploited?
@zware Maybe have a huge indentwidth and carefully configured string of whitespaces so that want gets very small?
Did you test it with real file in IDLE, not just by calling delete_trail_char_and_space()? I afraid that you will get hard time just displaying a long line containing 10000 tabulations and 10000 spaces.
@serhiy will do. Yes the dos is very non exploitable and not sure if idle is used in production anyways but since it’s reported let sfix
I disagree. If it is non-exploitable, it's not a DOS. Fixing it only encourages further reports of invulnerable vulnerabilities and a waste of volunteer time.
That said, there does appear to be some opportunity for cleanup here. My objection is to classifying the change as "fixing a DOS" rather than to using cleaner code, at the maintainer (@terryjreedy and/or @serhiy-storchaka)'s discretion.
@zware Good point! If so, we'll remove the fix for the have and want thing and only focus on the .lstrip and .rstrip part for <<<<...>>>>> since that makes the code cleaner. The have and want trimming space thing only reduces the time by a factor of the indent width at best which wouldn't be very high
That said, there does appear to be some opportunity for cleanup here. My objection is to classifying the change as "fixing a DOS" rather than to using cleaner code, at the maintainer (@terryjreedy and/or @serhiy-storchaka)'s discretion.
So turning the second quadratic into linear... not sure if it produces cleaner code though. Scanning backwards might be better instead of scanning forwards, because it saves some time... that said it's still a speedup by anywhere from 1-8x in normal usage.
Please don't keep merging main like that, it consumes CI resources unnecessarily. A merge is only really necessary to resolve conflicts or as a final check before merge, which is not the stage we're at here yet.
Please don't keep merging main like that, it consumes CI resources unnecessarily. A merge is only really necessary to resolve conflicts or as a final check before merge, which is not the stage we're at here yet.
Noted.
I don't use a lot idlelib so I don't know if there is a way to inject very long strings into it to trigger the bug. The rstrip/lstrip improvement can be isolated in a separate PR though, but for the bug in itself, we can just come up with a comment saying that it's unrealistic to trigger it.
However, I either want a proof that we can't trigger the DOS (or it's very hard to do so) or a PoC demonstrating that we can trigger it (not just some "we could do ...")